1.2.2. Проверочная матрица линейного кода

Поскольку линейный код V является подпространством, то для него существует ортогональное дополнение (или нулевое подпространство ). Ортогональное дополнение V " (n , k ) - кода V состоит из всех векторов длины n , ортогональных к каждому вектору v Î V . Векторы и называются ортогональными , если их скалярное произведение равно 0. Для двоичных векторов скалярное произведение равно сумме произведений соответствующих компонент. Например, скалярное произведение (00101, 10110) векторов 00101 и 10110 есть вектор 00100 = 0×1 + + 0×0 + 1×1 + 0×1 + 1×0. Ортогональное дополнение также является подпространством и, таким образом, может рассматриваться как линейный код. Множество V " - называется кодом, дуальным или двойственным к V.

Ортогональное дополнение V " (n , k ) - кода V имеет размерность (n - k) ; соответственно любой его базис состоит из (n -k) векторов. Порождающая матрица Н ортогонального дополнения называется проверочной матрицей кода V .

Т. к проверочная матрица состоит из базисных векторов ортогонального дополнения, то двоичный вектор с является кодовым словом, если и только если сН T = 0. Таким образом, проверка на наличие ошибок при передаче кодового слова сводится к умножению двух матриц вместо перебора всех кодовых слов. Умножение матриц, размерность которых составляет несколько тысяч, при современной вычислительной технике выполняется очень быстро.

Проверочную матрицу можно построить путем нахождения фундаментальной системы решений для соответствующей системы уравнений. Матрица

из предыдущего раздела порождает следующую систему уравнений:

Основная матрица системы совпадает с матрицей G . Неизвестные x 1 , x 2 и x 3 , для которых существует минор, не равный 0, можно объявить главными неизвестными. Тогда неизвестные x 4 и x 5 являются свободными. Мы выбираем для них линейно независимые значения 01 и 10 и получаем системы уравнений:

и

Из первой системы получаем x 1 = 1, x 2 = 0, x 3 = 1, т. е. решением исходной системы является вектор 10101. Из второй системы получаем x 1 = 1, x 2 = 1, x 3 = 0, т. е. вторым решением в фундаментальной системе решений является вектор 11010. Таким образом, получаем проверочную матрицу:

.

Заметим, что подобно порождающей матрице, для одного и того же кода существуют различные проверочные матрицы.

Связь кодового расстояния линейного кода и проверочной матрицы устанавливается следующей теоремой:

Теорема 1.3. Каждое не нулевое кодовое слово имеет вес не менее w , тогда и только тогда, когда любая совокупность из w столбцов матрицы Н

Доказательство. Для любого кодового слова с выполняется равенство сН T = 0. Пусть кодовое слово с имеет вес u . Исключим из рассмотрения нулевые компоненты вектора. Полученное равенство будет соотношением линейной зависимости u столбцов из Н . Следовательно, Н содержит множество из u линейно зависимых столбцов. Таким образом, в коде существует слово веса u , если и только если в матрице Н существует совокупность из u линейно зависимых столбцов. Таким образом, все не нулевые слова кода имеют вес не меньше w w -1 столбцов матрицы Н является линейно независимой.

Как следствие теорем 1.1 и 1.3 имеет место следующее утверждение:

Следствие. Расстояние линейного кода не менее w , если и только если любая совокупность из w -1 столбцов матрицы Н является линейно независимой.

Согласно сформулированным выше утверждениями, для того чтобы найти (п ,k )-код, исправляющий t ошибок, достаточно построить матрицу Н размерности (п - k ) × n , в которой любые 2 t столбцов линейно независимы.

Приведем матрицу H к треугольному виду:

Система уравнений:

Информационные символы:

Защитные символы:

Порождающая матрица

Информационные символы и соответствующие им защитные:

N	x 1 x 2 x 3 x 4	x 5 x 6 x 7	Вес

Есть черный ящик. L – совокупность преобразований в нем . L подействовала на X.

X 1 и x 2 не взаимодействуют между собой, поэтому это линейная система.

Св-во линейности кодов – сумма двух разрешенных кодовых слов равна разрешенному слову.

Билет 5.
а) Связь между ценностью информации и энтропией
б) Принципы построения линейных кодов. Декодирование по синдрому

Предположение, что множество выходных последовательностей канала является -мерным векторным пространством над полем GF(q}, а множество Y(n,R) входных последовательностей (код) является подпространством размерности nR. существенно облегчает декодирование. В этом случае Y(n,R) является подгруппой аддитивной группы , и, следовательно, может быть разложено на смежные классы по подгруппе . Пусть - все элементы (кодовые слова), тогда все элементы множества будут представлены с помощью стандартного расположения

(1)

(здесь через 0 обозначен единичный элемент группы ).

Каждая строка в (1) образующими элементами соответствующих смежных классов. Если в качестве образующих 0, е 1 , е 2 , ..., е s взяты элементы минимального веса в своем смежном классе, то любая последовательность из i-гo столбца отличается от у в меньшем числе разрядов, чем. от любого другого слова i¹K. Если в смежном классе, содержащем x, существует несколько элементов минимального веса, то найдется столько же кодовых слов, отличающихся от x в одном и том же наименьшем числе разрядов.

Для доказательства предположим, что x=y i +е, где е - элемент минимального веса в своем смежном классе. Очевидно, d{y i . x)=w (e) и d(y k ,x)=w(y k -y i -e). Если е- единственный элемент минимального веса, тоd(y i , x)K¹ i. Если таких элементов несколько (например, w(y j +e)=w(e)) , то d(y i , x)=d(y k , x) то при условии, что y k = y j –y i . Следовательно, для каждого элемента y j +e минимального веса в смежном классе, содержащем e, найдется слово y k = y j –y i , которое находится от у на расстоянии d(y k , i)=w(e).

Таким образом, для всех последовательностей x, входящих в 1-й столбец стандартной расстановки, условная вероятность Р(x\y i) максимальна. Если x находится в смежном классе с несколькими элементами минимального веса, то условная вероятность Р(x\у i)=Р(x\у k) и остается максимальной для всех у k , находящихся на одинаковом расстоянии от x

Правило декодирования может быть сформулировано следующим образом: найти выходную последовательность канала xÎ в (1) и считать, что была передана та последовательность y i ÎY(n.R), которая находится в том же столбце, что и x.

Очевидно, это правило совпадает с декодированием по максимуму правдоподобия и, следовательно, является оптимальным.

Правило декодирования линейного кода можно сформулировать так: после того. как выходная последовательность x; найдена в (1), определить наиболее вероятный вектор ошибки e, отыскивая образующий элемент того смежного класса, который содержит x; переданную последовательность найти из соотношения y=x-e.

Можно построить аналогичную процедуру декодирования, если воспользоваться однозначным соответствием между смежными классами и синдромами образующих элементов. Правило декодирования заключается в следующем : вычислить синдром принятой последовательности S= xH T =eH T ,

где e - образующий элемент смежного класса, содержащего x. По найденному синдрому S найти e; определить у из соотношения у= x-e.

Такое декодирование также совпадает с декодированием по максимуму правдоподобия и, следовательно, остается оптимальным. Первыми кодами с подобной процедурой декодирования были коды Хемминга, исправляющие одиночные ошибки.

Однако отыскание последовательности ошибок, когда число допустимых ошибок больше одной, быстро усложняется и при достаточно длинных кодах и большом количестве исправляемых ошибок становится практически невозможным.

Билет 6.
а) Энтропия и ее свойства

Проблема передачи непрер. сообщ-я закл. в получ. его копии на приемном пункте. Не сущ-ет способа, позвол-го получить точную копию перед-ого сообщ-я, поск. это требует бесконечной точности его воспроизв-я. Поэт. задают точность воспр-я перед-ого сообщ-я.

e-энтропии – это min кол-во инфы, кот. необх. передать по каналу, чт. восст. сообщение с заданной точностью при заданном распределении p(x) источника.

Модель передачи непр. сообщ-я:

d 2 = e 2 – ошибка при восст-нии сообщения y(t). Нужно установить связь м\д x(t) и x’(t), такую, чтобы x’ несло как можно меньшую инфу об x, но обеспечивало заданную точность.

He = min I (x, x’)

Каждому интервалу ставится в соотв-ие число. x = (b-a)/2 n .

чем > n, тем > интервалов и > точность.

I(x,x’)=H(x’) – H(x’/x) -взаимная инфа по опред-ию.

H(x’/x) = 0 т.к. значение случайной величины x определяет значение случайной величины x’ .

(“при фиксированном x ”)

I(x,x’)= H(x’) - кличество взаимной информации между множествами x и x’ равно энтропии x’ .

(опр-ся инф-ой ёмкостью регистра).

Пусть х равномерно распр. на интевале тогда все x’ равновероятны.

log[(b-a)/ x]=n величина энтропии ~ длине регистра

Надо обеспечить точность d 2 (среднеквадр. ошибка):

При min кол-ве взаимной инфы. Связь м\б x и x’ опр-ся кол-вом и длиной интервалов x. Надо их выбрать так, чт. x’ был распределён равномерно.

Пусть x и x’ непрерывны.

(1) x = x’ – n , где n – погрешн. кот. получается в рез-те апроксимации x x’-ом.

n=0, n 2 =d 2 e =e 2 –заданная ошибка

He =H(x)-max(H(n)), H(n) будет max при гауссовском распр. n

H(n)=/2

Источник чаще всего им. гауссовское распр. с d 2 , тогда: H(n) = /2 = log(d 2 x /d 2 n)/2 = log(d 2 x /e 2)/2 [бит/отсчёт]

Если за 1с. перед-ся 2F отсчётов, то Нe t = 2FHe = F*log(d 2 x /e 2) [бит/c]

По т.Шеннона для гаусс. канала: Нe t < F log(1+q 2) [бит/c]

б) Дискретизация непрерывных сообщений. Теорема Котельникова. Пространство сигналов.

Билет 7.
а) Взаимная информация и ее свойства

Кол-во информации, кот. Yj несет об Xi = кол-ву информации, кот. Xi несет об Yj. И эта информация называется взаимной информацией м-у Yj и Xi: . И она м.б. >0,<0,=0, в зависимости от средней информации.

Для каждой пары (Xi,Yj ) соответствует свое кол-во информации, а т.к. Xi и Yj – случайные величины, то и это кол-во информации случайно. Поэтому мы можем ввести понятие средней информации м-у множествами:

Отдельное состояние – это пара чисел .

I(X,Y)–полная взаимная информация (всегда ≥0, когда системы независимы).

Сделаем тождественные преобразования:

Тогда, взаимную информацию м. записать:

, (*)

С точки зрения информационного описания системы связи безразлично, какую из подсистем рассматривать в качестве передатчика, а какую в качестве приемника.

Поэтому энтропии Н (Х ) и H (Y ) можно интерпретировать как информацию, которая поступает в канал связи, а условные энтропии H (X/Y ), H (Y/X ) как информацию, которая рассеивается в канале.

Согласно теореме I (Х ,Y )≥0 мы получаем из (*):

Когда X и Y независимы, т.е. взаимн. инф-я =0

б) Адаптивная дискретизация непрерывных сообщений

Произвольную кусочно непрерывную функцию , изображающую сообщение или сигнал, можно разложить в обобщенный ряд Фурье по полной системе ортонормированных функций

если энергия функции конечна.

Бесконечная система действительных функций называется ортогональной на отрезке [ a, b ], если при , а отдельная функция называется нормированной, если .

Система нормированных функций в которой каждые две различающихся функции взаимно ортогональны, называется ортонормированной системой. При аппроксимации функции ограничиваются, как правило, конечным числом членов ряда. При заданной системе функций и при фиксированном числе членов ряда n значения коэффициентов можно выбрать такими, при которых среднеквадратичная ошибка аппроксимации

достигает минимума. Минимум среднеквадратичной ошибки достигается в том случае, когда коэффициенты ряда определяются по формуле . Ряд, с определяемыми таким образом коэффициентами, называется обобщенным рядом Фурье.

Ортогональная система называется полной, если путем увеличения количества членов в ряде среднеквадратичную ошибку можно сделать сколь угодно малой.

Таким образом, по счетному множеству коэффициентов можно с определенной

точностью восстановить соответствующую функцию можно заменить передачей последовательности коэффициентов . Указанную последовательность можно интерпретировать как вектор в n - мерном Евклидовом пространстве с координатами квадрат длины которого .

Последнее равенство является обобщением теоремы Пифагора на случай n-мерного пространства. Путем непосредственных вычислений легко установить, что энергия сигнала .

Таким образом, дискретизацией называется замена непрерывной функции последовательностью коэффициентов ... (вектором).

Выбор системы ортогональных функций определяется целью и физической сущностью решаемой задачи, а не чисто математическими умозаключениями.

С целью передачи сигнала по каналу связи широко применяется разложение функции в ряд Котельникова, которое позволяет существенно упростить определение коэффициентов . Согласно теореме Котельникова произвольная функция с ограниченным спектром, может быть тождественно представлена счетнывм числом ее значений, взятых через интервал времени где F - верхняя граничная частота спектра сигнала. В этом случае функции ,

образующие систему ортогональных функций, отличаются друг от друга только сдвигом по оси времени t на величину кратную , при этом каждая из них достигает своего максимального значения в те моменты времени, когда значения всех остальных функций равны нулю. Коэффициенты разложения определяются по формуле

,

которую в результате тождественных преобразований можно привести к виду: , то есть коэффициент равен значению функции в момент, когда функция достигает своего максимального значения.

Если дискретизации подлежит нормальный (гауссов) случайный процесс, энергетический спектр которого имеет прямоугольную форму, то коэффициенты будут статистически независимыми случайными величинами, которые совпадают со значениями случайной функции , взятыми с шагом Dt [ 9 ].

Таким образом, непрерывные сообщения можно передавать в цифровом виде, то есть в виде последовательности чисел, при этом каждое число приближенно выражает величину соответствующего коэффициента

Билет 8.
а) Эргодические источники. Производительность источника при независимых символах

б) Относительная энтропия непрерывных случайных величин

Относительной (дифференциальной) энтропией случайной величины Х называется величина

В частности, если интервал d = 1, то

Выясним физический смысл относительной энтропии H(X) .

Пусть источник сообщений вырабатывает последовательность значений случайной величины Х . После квантования получим последовательность значений случайной величины X ’ :

X i 1 ,X i 2 …..X ik …..X in .

При неограниченном увеличении длины последовательности с вероятностью, равной единице, появляются только типичные последовательности , число которых

где - число элементарного n -мерного кубика. Конец вектора, изображающего типичную последовательность, является внутренней точкой этого кубика. Произведение равно объему некоторой области в n -мерном пространстве, внутренние точки которой изображают концы типичных векторов (последовательностей). При , стремящемся к нулю, число типичных последовательностей стремится к бесконечности , а объем каждого элементарного кубика стремится к нулю . При этом объем V T , занимаемый типичными последовательностями, остается постоянным, равным .

Энтропию в дискретном случае можно было определить через число типичных последовательностей:

Аналогично относительную энтропию можно определить через объем V T , занимаемый типичными последовательностями:

В отличие от дискретного случая относительная энтропия может быть не только положительной, но и отрицательной, а также равной нулю . Чем больше объем V T , занимаемой типичными последовательностями, тем больше неопределенность того, какая из них появится. Единичному объему (V T =1) соответствует энтропия (неопределенность), равная нулю (H(X) =0). Это значение принимается за начало отсчета относительной энтропии.

В частности, относительная энтропия случайной величины с равномерным на единичном интервале (d = 1 ) распределением равна нулю:

В этом случае область n -мерного пространства, занимаемая типичными последовательностями, примерно совпадает с областью определения всех последовательностей и имеет форму куба единичного объема (V T = d n =1 ).

Билет 9.
а) Производительность марковского источника. Избыточность

Пусть x1, x2, ..., xk означают слово из k информационных битов на входе кодера, кодируемое в кодовое слово C размерности n битов:

вход кодера: X =[x 1, x 2, ...,xk ]

выход кодера: C =[c 1, c 2, ..., cn ]

Пусть задана специальная порождающая матрица G n , k ,

задающая блочный код (n ,k ).

Строки матрицы G n , k должны быть линейно независимы.

Тогда разрешенная кодовая комбинация C , соответствующая кодируемому слову X :

C =x 1 g 1 + x 2 g 2 + ... + x k g k .

Систематическая (каноническая) форма порождающей матрицы G размером k xn :

Порождающая матрица систематического кода создает линейный блочный код, в котором первые k битов любого кодового слова идентичны информационным битам, а остальные r =n -k битов любого кодового слова являются линейными комбинациями k информационных битов.

Проверочная матрица H n , k имеет r xn элементов, причем справедливо:

C xH T = 0.

Это выражение используется для проверки полученной кодовой комбинации. Если равенство нулю не выполняется, то получаем матрицу-строку ||c 1 , c 2 , ..., c r ||, называемую синдромом ошибки.

Код Хэмминга. Корректирующая и обнаруживающая способности. Правила выбора соотношения между длиной кодового слова и числом информационных битов. Формирование порождающей и проверочной матриц кода Хэмминга. Толкование синдрома ошибки

Рассмотрим код Хэмминга с кодовым расстоянием d =3, позволяющий исправлять одиночные ошибки (d =2q max +1).

Число разрешенных кодовых комбинаций для кода с d =3, для кода Хэмминга строго равно 2 n /(n +1). Первые k разрядов кодовых комбинаций кода используются в качестве информационных и их число равно

k = log 2 (2 n /(n +1)] = n – log 2 (n +1).

Данное уравнение имеет целочисленные решения k = 0, 1, 4, 11, 26, которые и определяют соответствующие коды Хэмминга: (3,1)-код, (7,4)-код, (15,11)-код и т.д. (всегда n =2 w ‑1).

Проверочная матрица H кода Хэмминга (r =n-k строк и n столбцов): для двоичного (n,k)-кода n=2 w -1 столбцов состоят из всех возможных двоичных векторов с r=n-k элементами, исключая вектор со всеми нулевыми элементами .

Легко проверить, что G xH T = 0 (нулевая матрица размером k xr элементов).

Пример. Проверим работу кода при передаче сообщения X =1011. Передаваемая кодовая комбинация будет сформирована в виде линейной комбинации (сложения по модулю 2) строк № 1, 3, 4 матрицы G 7,4:

Предположим, что на передаваемое кодовое слово C воздействовала ошибка 0000100, что привело к получению на приемной стороне слова C "=10111 10.

Тогда при перемножении C" на проверочную матрицу H T получаемматрицу-строку синдрома ошибки, которая соответствует тому столбцу проверочной матрицыH с номером бита, содержащего ошибку.

Сравнивая полученный синдром со строками H T , получаем, что ошибочен бит № 5 слева.

Декодер Хэмминга может работать в двух взаимоисключающих режимах:

Режим исправления (коррекции) ошибок (т.к. d min =3, то он позволяет исправлять одиночные ошибки);

Режим обнаружения ошибок (т.к. d min =3, то он обнаруживает ошибки кратности q £2). Если синдром не равен 0, то декодер выдает сигнал ошибки.

Если в принятом кодовом слове имеются 2 ошибки, а декодер работает в режиме коррекции, то он не сможет по синдрому определить, произошла ли одна ошибка или две, и выполнит неправильную коррекцию кодового слова.

Расширенный код Хэмминга. Режимы работы декодера, корректирующая и обнаруживающая способности. Формирование кодового слова. Формирование проверочной матрицы расширенного кода Хэмминга. Толкование синдрома ошибки

Расширение кода Хэмминга заключается в дополнении кодовых векторов дополнительным двоичным разрядом таким образом, чтобы число единиц, содержащихся в каждом кодовом слове, было четным. Благодаря этом коды Хэмминга с проверкой на четность обладают следующими преимуществами:

Длины кодов увеличиваются с 2 w -1 до 2 w , что удобно с точки зрения передачи и хранения информации;

Минимальное расстояние d min расширенных кодов Хэмминга равно 4, что дает возможность обнаруживать (!) 3-кратные ошибки.

Дополнительный разряд проверки на четность позволяет использовать декодер в новом гибридном режиме – обнаружения и коррекции ошибок.

Рассмотрим расширение (7,4,3)-кода Хэмминга.

Каждый кодовый вектор C a получается из кодового вектораc путем добавления дополнительного разряда проверки на четностьC a = (c 1 , ..., c 7, c 8), где .

Проверочная матрица H (8,4)-кода получается из проверочной матрицы (7,4)-кода в два приема:

К матрице (7,4)-кода дописывается нулевой столбец;

Полученная матрица дополняется строкой, полностью состоящей из одних единиц.

Получаем:

При синдромном декодировании

s " = C "ÄH T ,

причем все компоненты s" должны быть равны 0.

При одиночной ошибке s"(4) = 1. По значению синдрома (младшие 3 бита) находим и исправляем (инвертируем) ошибочный бит.

При двойной ошибке компонента s"(4)= 0, а синдром отличен от нуля. В отличие от стандартного кода Хемминга такая ситуация ужеобнаруживается , но не исправляется (передается запрос на повторную передачу слова и т.п.).

Таким образом, расширенный декодер Хэмминга может использоваться в одном из двух взаимоисключающих режимах:

Для исправления однократных и обнаружения двукратных ошибок;

Для обнаружения трехкратных ошибок.

Линейный систематический блочный код может быть также определён проверочной матрицей H , обладающей следующими свойствами. Если некоторая последовательность u является кодовым словом , то , т.е. проверочная матрица H ортогональна любой кодовой последовательности данного кода .

Проверочная матрица имеет размерность (n -k )×n и следующую структуру:

, (3.4)

проверочная часть единичная

матрицы подматрица

где
– транспонированная проверочная подматрица порождающей матрицы G ( k x n ) ;
- единичная подматрица.

Из свойств проверочной матрицы линейного блочного кода следует, что с ее помощью можно определить, является ли принятая последовательность кодовым словом данного кода .

Пример. Для рассмотренного примера линейного блочного (4, 7)-кода проверочная матрица имеет вид

.

Пусть принята последовательность с =(1011001). Проверим, является ли она кодовым словом:

=(1011001)
=(1 0 1 ) ≠ 0 .

Следовательно, последовательность (1011001) не является кодовым словом данного кода.

^

3.7 Синдром и обнаружение ошибки линейным блочным кодом

Пусть x =(х 1 , х 2 , …, х n ) – кодовое слово , переданное по каналу с помехами;

y =(y 1 , y 2 , …, y n ) – принятая последовательность, которая в силу влияния помех может отличаться от переданной.

Для описания возникающих в канале ошибок используется вектор ошибок е= (e 1 , e 2 , …, e n ) , который представляет собой двоичную последовательность длиной n с единицами в тех позициях, в которых произошла ошибка.

Например, вектор ошибок е =(0 0 0 1 0 0 0 ) означает однократную ошибку в четвертом бите, е =(1 1 0 0 0 0 0 ) – двукратную ошибку в первом и втором битах.

При передаче кодового слова x по каналу с шумом принятая последовательность будет иметь вид

y = x +е , (3.5)

где x - переданное кодовое слово; e – вектор, описывающий ошибки в канале.

Например, x =(0 0 0 1 0 0 0 ), e =(0 0 0 1 0 0 0 ). Тогда y =(0 0 0 0 0 0 0 ).

Чтобы проверить наличие ошибок в принятом векторе y , декодер вычисляет следующую (n -k ) - последовательность

S =(S 1 , S 2 , … S n - k )=y 
, (3.6)

где y – принятая кодированная последовательность; – проверочная матрица данного кода.

При этом вектор y является кодовым словом тогда, когда S =(0 0 … 0 ), и не является кодовым словом данного кода , если S ≠0.

Последовательность S служит признаком наличия ошибок в принятой последовательности и называется синдромом принятого вектора .

Некоторые сочетания ошибок, используя синдром, обнаружить невозможно. Например, если переданное кодовое слово x под влиянием помех превратилось в другое кодовое слово этого же кода, тогда синдром S =y ×
=0 , и декодер ошибки не обнаружит .

Пример. Для рассматриваемого примера линейного блочного (4, 7)-кода синдром определяют следующим образом.

Пусть x =(х 1 , х 2 , …, х 7 ) – принятая кодированная последовательность. Тогда

S =x 
=(х 1 ,х 2 ,… , х 7 )×
=((x 1 +x 3 +x 4 +x 5 ) , (x 1 +x 2 +x 3 +x 6 ) , (x 2 +x 3 +x 4 +x 7 ) ).

Циклические коды. Основные понятия и определения. Построить порождающую матрицу циклического кода с g(х) = 1+х+х*3

Циклические коды

Циклические коды - это целое семейство помехоустойчивых кодов, включающее в себя в качестве одной из разновидностей кодов Хэмминга, но в целом обеспечивающее большую гибкость с точки зрения возможности реализации кодов с необходимой способностью обнаружения и исправления ошибок, определяемой параметром d0, по сравнению с кодами Хэмминга (для которых d0=3 или d0=4). Одним из классов циклических кодов, способность исправлять многократные ошибки, являются коды БЧХ. Широкое использование циклических кодов на практике обусловлено также простотой реализации соответствующих кодеров и декодеров. Основные свойства и само название циклических кодов связаны с тем, что все разрешенные комбинации бит в передаваемом сообщении (кодовые слова) могут быть получены путем операции циклического сдвига некоторого исходного кодового слова:

Циклические коды задаются с помощью так называемых порождающих полиномов (многочленов) g(x) степени r = n-k, являющийся сомножителем двучлена x n +1, и их корней. Кроме того, вводятся понятия полинома исходного сообщения. Для этих полиномов, представляющих собой, по существу, альтернативную запись чисел в двоичной системе счисления, определяются операции сложения, умножения и деления, необходимые для организации кодирования и декодирования сообщения. Все эти операции выполняются по модулю 2.

Кодовые слова представляются в виде многочленов:

Основные параметры циклических кодов

Длина кода - n; Длина информационной последовательности - k; Длина проверочной последовательности - r=n-k; Кодовое расстояние кода - d 0 ; Скорость кода - R=k/n; Избыточность кода - R?; Вероятность обнаружения ошибки (искажения) - Р ОО; Вероятность не обнаружения ошибки (искажения) - Р НО.- коэффициенты из поля GF(q).

Основные понятия и определения

Кодовое расстояние между двумя кодовыми словами (расстояние Хэмминга) - это число позиций, в которых они отличаются друг от друга. Кодовое расстояние кода - это наименьшее расстояние Хэмминга между различными парами кодовых слов. Основные зависимости между кратностью обнаруживаемых ошибок t 0 , исправляемых ошибок t u , исправлением стираний t c и кодовым расстоянием d 0 кода:

Стиранием называется "потеря" значения передаваемого символа в некоторой позиции кодового слова, которая известна. Код, в котором каждое кодовое слово начинается с информационных символов и заканчивается проверочными символами, называется систематическим. Если код построен над полем GF(2), то коэффициенты принимают значения 0 или 1 и код называется двоичным. Длина циклического кода называется примитивной и сам код называется примитивным, если его длина n=q m -1 над GF(q). Если длина кода меньше длины примитивного кода, то код называется укороченным или непримитивным. Общее свойство кодовых слов циклического кода - это их делимость без остатка на некоторый многочлен g(x), называемый порождающим. Результатом деления двучлена x n +1 на многочлен g(x) является проверочный многочлен h(x). При декодировании циклических кодов используются многочлен ошибок e(x) и синдромный многочлен S(x). Многочлен ошибок степени не более (n-1) определяется из выражения

где - многочлены, отображающие соответственно принятое (с ошибкой) и переданное кодовые слова. Ненулевые коэффициенты в е(x) занимают позиции, которые соответствуют ошибкам. Синдромный многочлен, используемый при декодировании циклического кода, определяется как остаток от деления принятого кодового слова на порождающий многочлен, т.е.

Следовательно, синдромный многочлен зависит непосредственно от многочлена ошибок е(х). Это положение используется при построении таблицы синдромов, применяемой в процессе декодирования. Эта таблица содержит список многочленов ошибок и список соответствующих синдромов, определяемых из выражения (см. таблицу 4).

В процессе декодирования по принятому кодовому слову вычисляется синдром, затем в таблице находится соответствующий многочлен е(х), суммирование которого с принятым кодовым словом дает исправленное кодовое слово, т.е.

Перечисленные многочлены можно складывать, умножать и делить, используя известные правила алгебры, но с приведением результата по модулю 2, а затем по модулю x n +1, если степень результата превышает степень (n-1). Примеры.

Допустим, что длина кода n=7, то результат приводим по модулю x 7 +1.

При построении и декодировании циклических кодов в результате деления многочленов обычно необходимо иметь не частное, а остаток от деления. Поэтому рекомендуется более простой способ деления, используя не многочлены, а только его коэффициенты (вариант 2 в примере).

Циклический код может быть задан порождающей g(x) и проверочной h(x) матрицами. Для построения достаточно знать порождающий и проверочный многочлены. Для не систематического циклического кода матрицы строятся циклическим сдвигом порождающего и проверочного многочленов, т. е. путем их умножения на х.

Одна из основных задач, стоящих перед разработчиками устройств защиты от ошибок при передачи дискретных сообщений по каналам связи является выбор порождающего многочлена для построения циклического кода, обеспечивающего требуемое минимальное кодовое расстояние для гарантийного обнаружения и исправления t-кратных ошибок.

Существуют специальные таблицы по выбору порождающего многочлена в зависимости от предъявляемых требований к корректирующим возможностям кода. Однако у каждого циклического кода имеются свои особенности формирования порождающего многочлена. Поэтому при изучении конкретных циклических кодов будут рассматриваться соответствующие способы построения порождающего многочлена.