Лабораторные 101-104 (Методичка по лабам), страница 5

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

g₀ (x)x=x⁴+x²+x (010110).

Циклический сдвиг строки матрицы с единицей в старшем разряде (слева) равносилен умножению соответствующего многочлена на х с одновре­менным вычитанием из результата многочлена х^п+1

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

g_i(x)=g₀(x)xⁱ+С(xⁿ+1),

где С равно 1, если степень g₀(x)xⁱ превышает n-1, и нулю, если не превы­шает.

Если выбрать за образующий такой многочлен g₀(x), который является де­лителем двучлена xⁿ+1, то все многочлены матрицы, а поэтому и все много­члены кода (разрешенные кодовые комбинации), будут делиться на g₀ (x) без остатка. Ни один многочлен, соответствующий запрещенной кодовой комбина­ции, на образующий многочлен на цело не делится. Это свойство позволяет об­наруживать ошибки. По виду остатка можно определить и вектор ошибки, а, следовательно, и устранить ее.

Любая принятая кодовая комбинация h(x), содержащая ошибку, может быть представлена в виде суммы по модулю два неискаженной комби­нации кода f(x), делящейся на g₀(x) без остатка, и вектора ошибки e(x). Для од­нозначности декодирования каждому вектору ошибки должен соответствовать отличный от других остаток - опознаватель. Чем больше различных остатков может быть образовано при делении h(x) на g₀(x), тем больше разновидностей ошибок способен исправить данный циклический код.

Наибольшее число остатков, равное 2^m-1 (исключая нулевой), может обес­печить только неприводимый (простой) многочлен g₀(x) степени m , принадле­жащий показателю степени п, если m и n связаны соотношением n= 2^m-1.

В литературе по кодированию [1;2] доказано, что для любого т существует по крайней мере один неприво­димый многочлен степени т, принадлежащий показателю степени п, если n=2^m-1.

При известном числе информационных символов (к) задача, следова­тельно, сводится к тому, чтобы определить наименьшую степень т образую­щего многочлена, обеспечивающего обнаружение или исправление ошибок за­данной кратности. Зная п и т по имеющимся в ряде книг [2] таблицам много­членов, неприводимых при двоичных коэффициентах, можно выбрать и кон­кретный образующий многочлен.

Для исправления одиночных ошибок требуемая минимальная степень образующего многочлена (m) на­ходится из соотношения

2^т-1=2^п-k-1 C¹_n

Выберем, например образующий многочлен для случая к=4. Тогда п=7 и т=3.

В таблице неприводимых многочленов, принадлежащих степени п, нахо­дим два многочлена третей степени, так как х⁷+1=(х+1)(х³+х+1)(х³+х²+1).

Примем за образующий многочлен g(x)=x³+x²+1 (1101). Чтобы убедится, что каждому вектору ошибки соответствует отличный от других остаток, поде­лим каждый из этих векторов на g₀(x).

Векторы ошибок т младших разрядов имеют вид :

Степени соответствующих им многочленов меньше степени образующего многочлена g₀(x). Поэтому они сами являются остатками при нулевой целой части. Остаток, соответствующий ошибке в следующем разряде, получается при делении 1000 на 1101, т.е.

1000 1101

1101

101

Аналогично могут быть найдены и остальные остатки. Однако их можно получить проще, деля на g₀(x) комбинацию в виде единицы с рядом нулей и выписывая все промежуточные остатки

1 000000000 1101 Остатки

1101

1010 101

1101 111

1110 011

1101 110

01100 001

1101 010

001000 100

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

Если выбрать в качестве образующего многочлена , то тоже получим требуемое число различных остатков – 7.

Если k=5 и требуется исправлять тоже одиночную ошибку, то . Откуда получаем n_min=9 и m= n – k =9–5=4. Примем . Этот образующий многочлен сохранится до k=11, так как неравенство будет выполняться при n_min=15 и m=4.

3.2. Метод и средства кодирования

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

Применяется следующая процедура кодирования:

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

a(x)x^m=q(x)g₀(x)  r(x).

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

Полученный многочлен f(x)=a(x)x^m r(x)=q(x)g₀(x) делится на g(x) без ос­татка и, следовательно, соответствует разрешенной комбинации кода.

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

На рис.3.1 представлена схема, выполняющая деление произвольного мно­гочлена (например, многочлена а(х)=а_п-1х^п-1+а_п-2х^п-2+,...,+а₁(х)+а₀) на некоторый фиксированный (например, образующий) многочлен

g(x)=g^n-kх^п-к+...+g₁(x)+g₀.

Обратные связи регистра соответствуют виду многочлена g₀(x). КоличЕство включаемых в него сумматоров равно числу отличных от нуля коэффициентов g₀(x), уменьшенному на единицу. Это объясняется тем, что сумматор сложения коэффициентов старших разрядов многочленов делимого и делителя в регистр не включается, так как результат сложения заранее известен (он равен нулю).

За первые m тактов коэффициенты многочлена-делимого заполняют регистр, причем коэффициент при х в старшей степени достигает крайней пра­вой ячейки. На следующем такте единица делимого, выходящая из крайней ячейки регистра по цепи обратной связи, подается к сумматорам по модулю два, что равносильно вычитанию многочлена-делителя из многочлена-делимого. Если в результате предыдущей операции коэффициент при старшей степени х у остатка оказался равным нулю, то на следующем такте вычитания делителя не происходит. Коэффициенты делимого только сдвигаются вперед по регистру на один разряд, что находится в полном соответствии с тем, как это делается при делении многочленов столбиком.

Рис. 3.1 Схема деления на произвольный многочлен.

Деление заканчивается с приходом последнего символа многочлена-дели­мого. При этом разность будет иметь более низкую степень чем делитель. Эта разность и есть остаток.

Рассмотренная схема деления многочленов может использоваться при де­кодировании. При кодировании она не применяется в силу того, что между ин­формационными и проверочными символами образуется разрыв в m тактов.

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

Для случая g₀(x)=x³+x²+1 и а(х)=а³+1 схема кодирующего устройства приведена на рис. 3.2.

В исходном состоянии ключ К₁ находится в положении 1, а ключ К₂ замк­нут. Информационные символы одновременно поступают как в линию связи, так и в регистр сдвига, где за к тактов образуется остаток. Затем ключ К₂ раз­мыкается, ключ К₁ переходит в положение 2 и остаток выводится в канал связи.

Процесс формирования кодовой комбинации шаг за шагом представлен в табл. 3.1, где черточками отмечены освобождающиеся ячейки, занимаемые но­выми информационными символами.

Рис. 3.2 Схема кодирующего устройства.

Таблица 3.1

3.3. Метод и средства декодирования

Рассмотрим устройства декодирования, в которых для обнаружения и исправления ошибок производится деление произвольного многочлена f(x), со­ответствующего принятой комбинации, на образующий многочлен кода g₀(x). В этом случае при декодировании могут использоваться те же регистры сдвига, что и при кодировании.

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