Циклические коды, математическое описание, техника кодирования и декодирования.
Циклический код – это разновидность линейных блочных кодов (обладают теми же свойства ). Дополнительное свойство: комбинация, полученная после циклической перестановки символов в последовательности, взятой из кодовой таблицы, принадлежит той же таблице. Коды разрабатывались для того чтобы для кодирования и декодирования можно было использовать простые устройства.
для описания n-разрядных комбинаций s, состоящих из M-ичных символов, удобно использовать полиномы
 | (3.36) |
где sj=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)modg(x)=s(x)modg(x)+e(x)modg(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 символов принятой комбинации, начиная с v6 (старшего разряда). После завершения ввода в ячейках регистра оказывается записанным значение остатка 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. Благодаря этому ценному качеству среди всевозможных линейных блочных кодов именно циклические коды нашли наиболее широкое применение.