Теория информации (стр. 27 из 29)

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

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

f(x) = a(x)x^m + r(x)

Поскольку степень g(x) выбираем равной т, степень остатка r(х) не превышает m – 1. В комбинации, соответствующей многочлену а(х)х^т, т младших разрядов нулевые, и, следовательно, указанная операция сложения равносильна приписыванию r(х) к а(х) со стороны младших разрядов.

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

a(x)x^m = q(x)g(x) + r(x)

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

a(x)x^m+ r(x) = f(x) = q(x)g(x)

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

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

Равенства для определения проверочных символов могут быть получены путем решения рекуррентных соотношений:

(4.5)

где h-двоичные коэффициенты так называемого генераторного многочлена h(x), определяемого так

h(x) = (xⁿ + 1)/g(x) = h₀ + h₁x + … + h_kx^k

Соотношение (4.5) позволяет по заданной последовательности информационных сигналов a₀, a₁, ..., a_k-1вычислить n-kпроверочных символов a_k, a_k+1, ... ..., a_n-1. Проверочные символы, как и ранее, размещаются на местах младших разрядов. При одних и тех же информационных символах комбинации кода, получающиеся таким путем, полностью совпадают с комбинациями, получающимися при использовании предыдущего способа кодирования. Применение данного способа целесообразно для кодов с числом проверочных символов, превышающим число информационных, например для кодов Боуза-Чоудхури-Хоквингема.

4.10.7 Матричная запись циклического кода

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

M_n,k = || I_kC_k,n-k ||

Построение матрицы I_k трудностей не представляет. Если образование циклического кода производится на основе решения рекуррентных соотношений, то его дополнительную матрицу можно определить, воспользовавшись правилами, указанными ранее. Однако обычно строки дополнительной матрицы циклического кода С_k,n-k определяются путем вычисления многочленов r(х). Для каждой строки матрицы I_k соответствующий r(х) находят делением информационного многочлена а(х)х^т этой строки на образующий многочлен кода g(x).

Дополнительную матрицу можно определить и не строя I_k. Для этого достаточно делить на g(x) комбинацию в виде единицы с рядом нулей и получающиеся остатки записывать в качестве строк дополнительной матрицы. При этом если степень какого-либо r(х) оказывается меньше n – k – 1, то следующие за этим остатком строки матрицы получают путем циклического сдвига предыдущей строки влево до тех пор, пока степень r(х) не станет равной п-k— 1. Деление производится до получения kстрок дополнительной матрицы.

Пример 36. Запишем образующую матрицу для циклического кода (15,11) с порождающим многочленом g(x) = х⁴ + х³ + 1.

Воспользовавшись результатами ранее проведенного деления, получим

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

Матричная запись кодов достаточно широко распространена.

4.10.8 Укороченные циклические коды

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

Если, например, необходимо исправить единичные ошибки при k = 5, то нельзя взять образующий многочлен третьей степени, поскольку он даст только семь остатков, а общее число разрядов получится равным 8.

Следовательно, необходимо брать многочлен четвертой степени и тогда n= 15. Такой код рассчитан на 11 информационных разрядов.

Однако можно построить код минимальной разрядности, заменив в (n, k)-коде j первых информационных символов нулями и исключив их из кодовых комбинаций. Код уже не будет циклическим, поскольку циклический сдвиг одной разрешенной кодовой комбинации не всегда приводит к другой разрешенной комбинации того же кода. Получаемый таким путем линейный (n-j, k-j)-код называют укороченным циклическим кодом. Минимальное расстояние этого кода не менее, чем минимальное кодовое расстояние (n, k)-кода, из которого он получен. Матрица укороченного кода получается из образующей матрицы (n, k)-кода исключением j строк и столбцов, соответствующих старшим разрядам. Например, образующая матрица кода (9,5), полученная из матрицы кода (15,11), имеет вид

4.11 Технические средства кодирования и декодирования для циклических кодов

4.11.1 Линейные переключательные схемы

Основу кодирующих и декодирующих устройств циклических кодов составляют регистры сдвига с обратными связями, позволяющие осуществлять как умножение, так и деление многочленов с приведением коэффициентов по модулю два. Такие регистры также называют многотактными линейными переключательными схемами и линейными кодовыми фильтрами Хаффмена. Они состоят из ячеек памяти, сумматоров по модулю два и устройств умножения на коэффициенты многочленов множителя или делителя. В случае двоичных кодов для умножения на коэффициент, равный 1, требуется только наличие связи в схеме. Если коэффициент равен 0, то связь отсутствует. Сдвиг информации в регистре осуществляется импульсами, поступающими с генератора продвигающих импульсов, который на схеме, как правило, не указывается. На вход устройств поступают только коэффициенты многочленов, причем начиная с коэффициента при переменной в старшей степени.

Рис. 4.9.

На рис. 4.9 представлена схема, выполняющая умножение произвольного (например, информационного) многочлена

a(x) = a₀ + a₁x + … + a_k-1x^k-1

на некоторый фиксированный (например, образующий) многочлен

g(x) = g₀ + g₁x + … + g_n-kx^n-k.

Произведение этих многочленов равно

a(x)g(x)=a₀g₀ + (a₀g₁ + a₁g₀)x + … +(a_k-2g_n-k + a_k-1g_n-k-1)x^n-2 +a_k-1g_n-kx^n-1

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

На первом такте на вход схемы поступает первый коэффициент а_k-1 многочлена а(х) и на выходе появляется первый коэффициент произведения, равный

a_k-1g_n-k

На следующем такте на выход поступит сумма

a_k-2g_n-k + a_k-1g_n-k-1 ,

т.е. второй коэффициент произведения, и т. д. На n-м такте все ячейки, кроме последней, будут в нулевом состоянии и на выходе получим последний коэффициент а₀g₀