Систематический циклический код

Построение кодовых полиномов непосредственным перемножением информационного и порождающего полиномов не приводит к систематическим кодовым словам.

Пример 5.3.1 Воспользуемся для построения двоичного (7,4) циклического кода порождающим полиномом g(z)=z³+z+1 (см. пример 5.2.1).

Сообщению (1110) отвечает информационный полином a(z)=z²+z+1. При этом кодовый полином, получаемый прямым перемножением a(z) и g(z): u(z)=a(z)g(z)=(z²+z+1)(z³+z+1)=z⁵+z⁴+1, соответствует слову (1000110), не содержащему явно информационных битов в начале либо конце, т.е. не являющемуся систематическим.

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

предписывающим умножение информационного полинома на z^r=z^n–k (другими словами, сдвиг информационных битов на n–k позиций вправо) и вычитание из полученного результата остатка r(z) от деления его на порождающий полином g(z). Полученный так полином u(z) делится на g(z), а значит, все кодовые полиномы остаются прежними – всеми полиномами степени не большей n–1, делящимися на g(z). Единственное, что изменилось в результате описанной модификации кода – теперь k старшими коэффициентами u(z) оказались информационные биты, т.е. на k последних позициях кодового вектора разместились «чистые» информационные биты.

Пример 5.3.2 Для условий примера 5.3.1 z^n–ka(z)=z³(z²+z+1)= z⁵+z⁴+z³, что после деления на g(z) дает остаток r(z)=z. В итоге u(z)= z⁵+z⁴+z³+z, и соответствующий кодовый вектор U=(0101110) имеет систематическую структуру, в которой информационные биты занимают последние k позиций.

Порождающая и проверочная матрица циклического кода

Как и любой линейный, циклический код может быть задан с помощью порождающей и проверочной матриц. Что касается порождающей матрицы, ее структура напрямую следует из систематического представления кодовых полиномов. Рассмотрим k «базисных» информационных векторов: a₁=(10…00), a₂=(01…00), … , a_k=(00...01), чьи информационные полиномы после умножения на z^n–k принимают вид
z^n–ka₁(z)=z^n–k, z^n–ka₂(z)=z^n–k+1, … , z^n–ka_k(z)=z^n–1. После нахождения систематических кодовых полиномов u_i(z)=z^n–ka_i(z)–r_i(z), i=1,2, …, k,получатся k кодовых векторов вида u₁=(r₁ ¦ a₁), u₂=(r₂ ¦ a₂), …, u_k=(r_k ¦ a_k), где r_i – (n–k)-мерные векторы коэффициентов остатков r_i(z), i=1,2, …, k. Линейная независимость этих кодовых векторов позволяет использовать их как базис кода, т.е. построить порождающую матрицу последнего как

Если систематичность кода не является непременным условием, порождающая матрица легко строится непосредственно по порождающему полиному: строки ее – это попросту k циклических сдвигов n-мерного вектора коэффициентов порождающего полинома. Подобным же образом несистематическая проверочная матрица напрямую получается из проверочного полинома h(z)=h_kz^k+h_k-1z^k–1+…+h₀:

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

Линейность циклических кодов означает безоговорочную применимость к ним всех методов кодирования и декодирования, рассмотренных в предыдущей главе. В то же время свойство цикличности зачастую открывает дополнительные возможности упрощения кодера в аппаратной реализации. Так, если приемлем несистематический вариант кода, структура кодера оказывается особенно простой. Поскольку любой кодовый полином u(z) такого кода есть произведение информационного a(z) и порождающего g(z) полиномов, компоненты соответствующего кодового вектора uявляются сверткой информационной последовательности a₀, a₁, … , a_k–1 с последовательностью коэффициентов порождающего полинома g₀, g₁, … , g_n–1.

Подобная операция реализуется фильтром с конечной импульсной характеристикой (КИХ–фильтром) вида

Обратимся теперь к структуре систематического циклического кодера. Согласно сказанному в параграфе 7.3, ключевой операцией в построении систематического кодового полинома циклического кода является нахождение остатка r(z) от деления произведения z^n–ka(z) на порождающий полином g(z). Чтобы понять, каким образом структура, представленная далее, вычисляет r(z), разделим z^n–ka(z)=a_k–1z^n–1+a_k–2z^n–2+…+a₀z^n–k на g(z)=z^r+g_r–1z^r–1+ +…+g₀, используя правило длинного деления. На первой итерации g(z) умножается на a_k–1z^n–r–1 и результат вычитается из делимого.

В итоге первый остаток r₁(z)=r_1,n–2z^n–2+r_1,n–3z^n–3+…+r_1,n–r–1z^n–r–1 имеет степень не более n–1 и после сложения с a_k–2z^n–2 используется на второй итерации как новое делимое. При выполнении второй итерации из него вычитается (r_1,n–2+a_k–2)z^n–r–2g(z) , давая второй остаток r₂(z)=r_2,n–3z^n–3+r_2,n–4z^n–4+…+r_2,n–r–2z^n–r–2, степень которого не превышает n–3. Остаток r₂(z) вновь суммируется с a_k–3z^n–3 и используется как делимое на третьей итерации и т.д. Легко видеть, что на i-й итерации предыдущий остаток, сложенный с
a_n–iz^n–i, служит делимым, из которого вычитается произведение полинома g(z) на z в степени, уравнивающей степени вычитаемого и делимого, а также на коэффициент, равный старшему коэффициенту делимого. Результатом этого оказывается очередной остаток, с которым производятся те же действия на следующей итерации. После k итераций k-й остаток имеет степень, меньшую r, являясь, очевидно, требуемым остатком r(z). Подобное «длинное деление» реализуется систематическим циклическим кодером, показанным на предыдущем слайде и основанным на регистре сдвига с линейной обратной связью.

Исходно ключ S1 замкнут, а ключ S2 находится в положении 1. Биты данных подаются на вход, начиная со старшего a_k–1. Допустим, что в r ячейках регистра сдвига записаны коэффициенты текущего делимого. Тогда в точке B присутствует старший коэффициент текущего делимого, а в точках C₀ … C_r–1 – его произведения с коэффициентами порождающего полинома. Следовательно, в точках B₁…B_r–1 формируются коэффициенты разности текущего делимого и порождающего полинома, умноженного на старший коэффициент делимого и соответствующую степень z,т.е. коэффициенты следующего остатка. При подаче тактового импульса эти коэффициенты записываются в ячейки регистра, подготавливая его к новой итерации. После k итераций регистр содержит остаток r(z), и, чтобы передать последний на выход, ключ S1 размыкается, а S2 переводится в положение 2. В результате на выходе после бита данных a₀ следует старший коэффициент r(z) (первый проверочный символ), и т.д.

Пример 5.5.1 Кодер (7,4) кода из примера 5.3.2 приведен на следующем слайде. Там же дана таблица, содержащая значения информационных битов, состояние регистра и выходное слово. Как видно, при прежнем информационном полиноме a(z)=z²+z+1 последняя колонка таблицы, читаемая снизу вверх, совпадает со словом, полученным в примере 5.3.2.