Циклические коды, математическое описание, техника кодирования и декодирования.

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

для описания n -разрядных комбинаций s, состоящих из M -ичных символов, удобно использовать полиномы

(3.36)

где s_j =0; 1;…; M -1.

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

,

(3.40)

где , причём всегда . Формально этот полином тоже содержит n членов, просто у него при .

Фундаментальное свойство циклического кода состоит в том, что полином s(x), соответствующий любой разрешённой (передаваемой) комбинации s, делится без остатка на производящий полином

.

(3.41)

Отсюда следует метод декодирования принимаемой комбинации v (x): нужно вычислить остаток res(x) от деления этого полинома на g (x). Степень полинома res(x) не превышает r -1, то есть этот остаток содержит r бит. Если оказалось, что , то это несомненно указывает на наличие ошибок в принятой комбинации (обнаружение ошибок).

Напомним, что переданная s и принятая v комбинации связаны соотношение (3.2), откуда следует

v (x)= s (x)+ e (x),

(3.42)

где e (x) – полином ошибок. Тогда с учётом (3.41) имеем соотношение, аналогичное формуле (3.17),

res(x)= v (x)mod g (x)= s (x)mod g (x)+ e (x)mod g (x)= e (x)modg(x),

(3.43)

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

Во-первых,

,

(3.47)

где р – целое число ;

,

(3.48)

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

Во-вторых,

(3.49)

для любого b (x), если и . Это значит, что многочлен g (x) является неприводимым (простым), то есть не делится без остатка ни на какой другой многочлен, кроме 1 и самого себя.

В-третьих,

,

(3.50)

то есть двучлен делится без остатка на g (x) (сравните это с формулой (3.18)).

 

Кодирование в несистематическом виде:

s (x)= a (x) g (x),

(3.45)

Для кодирования в систематической форме

.

(3.46)

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

1) умножение a (x) на означает, что k информационных символов сдвигается на r позиций вправо и в итоге занимают k старших (по степеням x) разрядов; r разрядов слева при этом оказываются нулевыми;

2) вычисляется r -разрядный остаток res(x) от деления полинома , соответствующего полученной таким образом комбинации;

3) эти r элементов остатка помещаются на r нулевых позиций комбинации, полученной в пункте 1, в качестве проверочных символов.

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

,

(3.54)

где - полином, согласованный с h (x), то есть коэффициенты этого полинома записаны в обратном порядке . Например, при n =7 для имеем .

Рассмотрим пример. код (7,4). производящий полином: .

Схема кодера, реализующего метод (3.45), приведена на рис. 3.3. Ячейки регистра обнуляются, затем при замкнутом ключе K в кодер вводятся 4 информационных символа, при этом в схеме вычисляются и выводятся 4 первых символа кодовой комбинации. Далее ключ K размыкается, и в течении следующих трёх тактов вычисляются и выводятся значения .

Схема кодера систематического кода, реализующая метод (3.46), дана на рис. 3.4.

Это схема деления полинома на полином g (x), но, в отличие

 

 

 

 

от схемы рис.2.11, она построена несколько иначе, поскольку ориентирована не на вычисление частного, а на вычисление остатка. Регистр обнуляется, переключатель П переводится в положение 2, и

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

Схема декодера, приведённая на рис. 3.5, также ориентирована на вычисление остатка от деления полинома v (x) на полином g (x). Регистр обнуляется, ключ K замыкается, и в течение 7 тактов в регистр вводятся 7 символов принятой комбинации, начиная с v ₆ (старшего разряда). После завершения ввода в ячейках регистра оказывается записанным значение остатка res(x). Если res(x)=0 (в 3 ячейках регистра оказались нули), считают, что в принятой комбинации ошибок нет, и на этом декодирование заканчивается.

В противном случае , ключ К размыкается (фактически это соответствует ситуации, когда последующие входные символы равны нулю), и подают ещё 7 тактовых импульсов, формально продолжая процесс деления. Номер такта, на котором в ячейках регистра оказывается комбинация 100 (это случай res(x)=1, учитывается обратный порядок следования символов), и есть номер ошибочного символа. После этого исправление этого символа и отделение информационных символов – это тривиальные операции.

Чтобы не было сомнений, заметим, что ожидаемая комбинация 100 в течение 7 тактов обязательно появится, причём один раз. Дело в том, что при отключении входа схема рис. 3.5 превращается в генератор двоичной псевдослучайной М-последовательности с периодом (2.21) равным 7. Свойства М -последовательности таковы, что в течение периода в ячейках генератора обязательно по одному разу оказываются записанными все r -разрядные двоичные комбинации, кроме нулевой, разумеется.

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

Как показывает практика, формальное запоминание приведённых соотношений и схем мало что даёт для понимания сути вопроса, если детально не разобрать хотя бы десяток конкретных численных примеров. В частности, если нужно закодировать информационную последовательность 0011, для которой , то, проследив такт за тактом работу схемы рис.3.4 и записывая содержимое ячеек, можно убедиться в том, что на выходе появится комбинация 1100010, которой соответствует полином (значение этого полинома вычислите отдельно по формуле (3.46) и сравните с комбинацией).

В заключение обязательно нужно отметить следующее обстоятельство. Благодаря циклическому свойству, при кодировании и декодировании циклического кода удаётся организовать конвейерную обработку длинных последовательностей символов в устройствах, содержащих удивительно малое количество простейших логических элементов. Например, для кода (255,247) кодер и декодер содержат по 8 ячеек регистра сдвига и по 4 сумматора по модулю 2. Благодаря этому ценному качеству среди всевозможных линейных блочных кодов именно циклические коды нашли наиболее широкое применение.