Лекция 15

Решение: n-k=7-4=3, тогда f(x)* x^n-k = (x³+x+1)x³ = x⁶+x⁴+x³.

с остатком r(x)=x². Таким образом, искомая кодовая комбинация = x⁶+x⁴+x³+x² или в двоичном виде 1011100, где левые четыре разряда представляют собой информационные разряды, соответствующие полиному f(x)=x³+x+1, а остальные три разряда – контрольные, соответствующие полиному r(x)=x².

Таким образом, выявлено первое свойство образующего полинома g(x), состоящее в том, что все разрешенные комбинации данного кода делятся на него без остатка. Он позволяет выбрать из большого числа комбинаций только те, которые удовлетворяют заданному закону построения кода, т.е. разрешенные. Именно поэтому полином g(x) и называется образующим.

Степень l образующего полинома g(x) не может быть меньше требуемого числа контрольных разрядов n-k. Для упрощения обычно полагают l=n-k. Но не любой полином этой степени может выступать в качестве образующего полинома циклического кода. В качестве таковых могут использоваться только так называемые неприводимые полиномы. Полином называется приводимым, если он может быть представлен в виде произведения полиномов низших степеней, в противном случае полином называется неприводимым. Другими словами, неприводимый полином делится без остатка только на самого себя и на единицу. Неприводимые полиномы играют роль, сходную с простыми числами в теории чисел. Из нескольких неприводимых полиномов данной степени в качестве образующего полинома следует выбирать самый короткий, однако число ненулевых членов g(x) не должно быть меньше требуемого кодового расстояния кода.

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

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

Пример 3.11. Построить образующую матрицу циклического кода (7,4) с образующим полиномом g(x)=x³+x+1.

Решение.

Запишем базовые информационные комбинации:

Представим их в виде полиномов:

Умножим на x^n-k=x³

Поделим каждый из них на образующий полином и зафиксируем остаток:

	Частное	Остаток

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

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

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

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

Метод получения канонической формы проверочной матрицы циклического кода аналогичен рассмотренному ранее общему для групповых кодов методу, т.е. .

Тогда для рассматриваемого циклического кода с образующим полиномом g(x)=x³+x+1 проверочная матрица будет выглядеть следующим образом .

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

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

Следовательно, при делении на g(x) получим .

При наличии однократной ошибки в каком-либо информационном разряде полиномы ошибок имеют вид:

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

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

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

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

1. Число разрядов регистра, т.е. число триггеров, выбирается равным числу проверочных разрядов n-k, т.е. равным степени образующего полинома.

2. Число двухвходовых сумматоров по модулю два берется на единицу меньше числа членов образующего полинома.

3. Триггеры регистра нумеруются слева направо от 1 до n-k.

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

5. Выходы предыдущих триггеров соединяются с входами последующих через сумматоры по модулю два там, где они есть, или непосредственно, там, где их нет.

6. На второй вход сумматора по модулю два, первый вход которого соединен с выходом последнего триггера с номером n-k подаются в последовательном коде информационные разряды, т.е. этот вход является входом кодера. Выход этого сумматора соединяется с входом первого триггера и вторыми входами всех остальных сумматоров по модулю два.

После того, как все k информационных разрядов последовательно поступят в кодер, одновременно будучи выданными в линию, в триггерах регистра будет сформирован остаток, состоящий из n-k контрольных символов, которые должны быть переданы вслед за информационными. Для управления этим процессом в структуру кодера необходимо ввести три ключа К1, К2, К3. Ключи К1 и К2 необходимы для того, чтобы коммутировать выход кодера либо с входом кодера при передаче k информационных разрядов, либо с выходом регистра при передаче n-k контрольных разрядов. Чтобы эти уже сформированные разряды выдвигались из регистра без искажений, необходимо разорвать цепь обратной связи, для чего и служит ключ К3.

С учетом всего сказанного построим структуру кодера (рис. 3.12) циклического кода (7,4) с образующим полиномом g(x)=x³+x+1.

Рис. 3.12

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

Построенная в соответствии с этим полиномом структура кодера приведена на рис. 3.13.

Работа кодера начинается с того, что в регистр с отключенной обратной связью (0 на входе управления) заносятся четыре информационных символа (старший разряд в Т4). Затем обратная связь включается (1 на входе управления) и регистр сдвигается семь раз. Первые четыре символа, поступающие с выхода кодера, являются информационными, следующие за ними три символа – контрольными.

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

Рис. 3.13

Дешифратор остатка может быть реализован по-разному в зависимости от того, в каком режиме используется данный код: только для обнаружения ошибок или для исправления ошибок.

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

Рис. 3.14

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

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

Рис. 3.15

Для увеличения кодового расстояния циклического кода может быть использовано преобразование расширения кода, выполняемое за счет введения дополнительных контрольных разрядов. Одним из простейших способов расширения кода является введение одного контрольного разряда общей проверки на четность. В результате, например, циклический код (7,4) с образующим полиномом превратиться в циклический код (8,4) с образующим полиномом , поскольку полином (x+1) является образующим для циклического кода с одним контрольным разрядом, способным обнаруживать все ошибки нечетной кратности. Отсюда (попутно) можно сделать вывод о том, что код с проверкой на четность является циклическим кодом с образующим полиномом (x+1). Полученный расширенный код с d=4 будет обладать такими же корректирующими свойствами, что и аналогичный расширенный код Хэмминга. Можно сделать обобщение, состоящее в том, что для любого кода с нечетным кодовым расстоянием введение общей проверки на четность увеличивает кодовое расстояние на 1.

Если далее над этим кодом выполнить операцию укорочения, состоящую в удалении одного информационного разряда, то получится код (7,3) с d=4 и проверочной матрицей .

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

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

,

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

Если число уравнений, входящих в каждую ортогональную систему, не меньше s, то путем голосования по большинству могут быть исправлены любые ошибок. В самом деле, ошибка в одном символе влияет в силу ортогональности не более чем на одну проверку, следовательно, среди значений символа a_j, которые получены из всех s проверок, неправильными могут оказаться не более t, т.е. не более половины уравнений. Тогда, сравнивая значения правых частей проверок, а также значение самого символа a_j, можно по большинству значений определить верное значение этого символа. Если при нечетном s имеет место равенство голосов, то ошибка обнаруживается, но не исправляется.

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

Именно к таким кодам относится код (7,3), проверочная матрица которого получена ранее в результате последовательных операций расширения и укорочения циклического кода. Пользуясь ею , можно записать систему проверочных уравнений

.

Суммируя по модулю два второе и третье уравнения и разрешая полученные три уравнения относительно а₇, получаем систему

,

отвечающую сформулированным ранее условиям ортогональности.

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

Анализируя указанным выше способом каждый символ принятой кодовой комбинации можно правильно восстановить посланную кодовую комбинацию, если произошло не более одной ошибки, или обнаружит двойную ошибку. Тем самым полностью реализуются корректирующие способности этого кода, поскольку его кодовое расстояние d=4.

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

Важнейшие классы полиномиальных кодов

Коды БЧХ. Циклический код, исправляющий более одной ошибки, т.е. код с d ³ 5, в общем случае можно построить следующим образом:

а) по заданному k определить необходимое для исправления одной ошибки n-k и построить (n,k)-код описанным ранее методом;

б) рассматривая этот (n,k)-код как некорректирующий n-разрядный код, определить количество n₁-n дополнительных контрольных разрядов для обеспечения исправления одной ошибки в этом коде и построить тем самым (n₁,n)-код;

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

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

Заданными при кодировании с помощью БЧХ-кодов является число ошибок s, которое требуется исправлять, и общая длина кодовой комбинации n. На выбор величины n накладывается ограничение: n=2^f – 1, где f – любое целое число больше нуля. Число информационных символов k и число контрольных символов n-k и их состав подлежат определению.

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

(3.33)

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

Образующий полином g(x) БЧХ-кода находится как наименьшее общее кратное (НОК) так называемых минимальных полиномов до номера 2s-1 или d-2 включительно, т.е. g(x) = НОК [M_i(x)], где i = 1,3,5, . . ., 2s-1 – номера минимальных полиномов. Поскольку минимальные полиномы по определению являются простыми и неприводимыми, то, условившись об отбрасывании возможных одинаковых M_i(x), можно НОК заменить произведением полиномов

, (3.34)

число которых в этом произведении L=s. Далее определяется старшая степень j минимального полинома. Степень j есть такое наименьшее число, при котором 2^j – 1 нацело делится на n, отсюда следует, что j=f. После того, как определены число минимальных полиномов и старшая степень полинома, сами полиномы, из которых составляется произведение (3.34) выписываются из справочных таблиц. При этом, если в таблицах отсутствует полином нужного номера данной степени, то следует взять ближайший с нужным номером, но меньшей степени. Кроме того, если среди выбранных полиномов окажутся два одинаковых, то в (3.34) включают только один из них. После того, как (3.34) сформировано, можно определить степень b образующего полинома g(x), перемножив входящие в него полиномы, при этом

. (3.35)

Знак нестрогого равенства появился как результат того, что степени некоторых M_i(x) могут быть меньше j.

Далее можно определить число контрольных разрядов n-k, которое по определению равно степени образующего полинома, т.е. n-k = b, после чего становится возможным и определение числа информационных разрядов k=n-(n-k). Если получившееся k окажется меньше требуемого для передачи заданного объема информации, необходимо перейти к следующему по порядку разрешенному n=2^f – 1 и выбрать для формирования g(x) минимальные полиномы степени f. Далее по описанной ранее методике для обычных циклических кодов при известном g(x) могут быть построены образующая и проверочная матрицы кода и, тем самым, код полностью построен и описан. Минимальные полиномы различных степеней и номеров являются справочными данными.

Для декодирования БЧХ-кодов могут быть использованы как алгоритмы анализа остатка от деления и мажоритарного декодирования, так и другие алгоритмы.

Важнейший подкласс БЧХ-кодов образуют коды Рида – Соломона, являющиеся недвоичными БЧХ-кодами. Они достаточно широко используются в системах двухуровневого каскадного кодирования.

Коды максимальной длины. Кодами максимальной длины называются циклические коды с параметрами (2^k-1, k), у которых в качестве образующего полинома выбран проверочный полином, полученный описанным ранее образом. Например, требуется построить код (15,4) максимальной дины. Выбрав по описанным выше правилам примитивный полином четвертой степени, например x⁴ + x + 1, найдем для него проверочный полином, который и будет образующим полиномом для кода (15,4) максимальной длины . Этот полином является полиномом кодовой комбинации кода. Остальные 14 ненулевых кодовых комбинаций являются четырнадцатью циклическими сдвигами этой комбинации (полинома). Отсюда вытекает одно важное свойство этих кодов. Поскольку все ненулевые комбинации являются циклическими сдвигами одной ненулевой комбинации, то все комбинации этого кода имеют один и тот же вес. Такие коды называются эквидистантными или симплексными. Кодеры для таких кодов иногда называют регистрами сдвига с линейными обратными связями, формирующими последовательности максимальной длины. Они имеют несколько различных применений. При большом числе разрядов такой регистр формирует последовательность с очень хорошими свойствами случайности. Такие устройства используются на практике в качестве генераторов псевдослучайных последовательностей.

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

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

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

Образующий полином кода Файра определяется выражением , где g(x)- неприводимый полином степени m, причем m>b, где b- длина исправляемого пакета ошибок, а c³2b-1, причем с должно выбираться таким, чтобы оно не делилось нацело на число e=2^m-1. Число контрольных разрядов в кодовой комбинации кода Файра определяется по формуле n-k = c+m, а общее число разрядов в кодовой комбинации n находится как наименьшее общее кратное чисел с и е, т.е. n = НОК(с,е).

Коды Файра являются высокоскоростными кодами с малой избыточностью. Если использовать код БЧХ с той же корректирующей способностью, то он будет обладать большим коэффициентом избыточности. Вывод очевиден, поскольку исправить ошибки, сгруппированные в пакет проще, чем ошибки, рассредоточенные по всей длине комбинации.