Лабораторная работа: Программный кодер-декодер для циклических (n,k)-кодов
(7)
Здесь 
т.е. является проверочными битами кодового слова.
7.2 Алгоритм кодирования
Известно на старте:
– длина выходных кодовых слов n ;
– длина входной последовательности k ;
– число контрольных бит (n-k)=r ;
– порождающий многочлен G (x) ;
Назначается величина ℓ≤ r . Вычисляются параметры s и m0 . В памяти машины организуется 2ℓ строк («мест»). В каждую строку для каждой конфигурации двоичного отрезка длины ℓ пишется остаток, вычисленный заранее по изложенному выше алгоритму. В процессе кодирования процедура деления заменяется считыванием из памяти остатка для очередного ℓ -отрезка кодируемой последовательности. Это существенно повышает быстродействие программного кодера при (обычно) приемлемом расходе памяти. Желательно так писать программу, чтобы ℓ -отрезок мог выступать в роли «смещения» по адресному пространству списка остатков.
Алгоритм кодирования сводится к следующему.
1. Из исходной k‑ битовой информационной последовательности со стороны левых («старших») разрядов выделяется отрезок длины ℓ и из таблицы выбирается соответствующий ему остаток.
2. Полученный остаток суммируется по mod2 с левыми разрядами оставшейся части блока длиной (k-ℓ ) бит.
3. Из полученной суммы со стороны левых разрядов выделяется очередной ℓ -отрезок, для которого из таблицы считывается соответствующий остаток и т.д.
4. Через (s‑1) таких шагов из полученной суммы выделяются m0 старших разрядов ℓ-m0 и для сформированной ℓ- разрядной комбинации выбирается соответствующий остаток из таблицы.
5. Полученный остаток суммируется по mod 2 с оставшимися (после выделения m0 разрядов) битами. Эта сумма является комбинацией проверочных разрядов циклического кода.
8. Содержательный пример [3]
Методом деления по частям построить кодер для циклического (15,11) – кода, заданного порождающим многочленом G ( x )=х4 +х+1 .
Здесь n =15; k =11. Выбираем ℓ =4. Тогда s =3, m0 =3. Всего имеем 2ℓ различных конфигураций ℓ -отрезков. Остатки, соответствующие этим отрезкам, вычисленные в соответствии с алгоритмом деления по частям, приведены в табл. 1.
Пусть входная (информационная) последовательность, разделенная на отрезки, имеет вид: 1101 1000 110
Выбираем первый ℓ -отрезок 1101 и выбираем из таблицы соответствующий остаток 0100. Складываем по mod 2 со следующим отрезком 0100+1000=1100. Полученной сумме соответствует остаток 0111. Поскольку сделано уже (s‑1) шагов, прибавим этот остаток к оставшимся трем битам 0111+110=1011. На этот результат понадобится ссылка, поэтому присвоим ему наименование U s-1 . Из полученной суммы выделим m0 левых бит и дополним их слева нулями до размерности ℓ (в данном случае – одним нулем). Получим 0101. Из таблицы найдем остаток – 1111. Выполняется s ‑й шаг деления. Оставшуюся «1» (справа) от U s-1 , из которого выделяли m0 левых бит, сложим со стороны старших разрядов с только – что полученным остатком 1111+1=0111. Это и есть контрольные биты к информационной последовательности 1101 1000 110.
Результат можно проверить традиционным делением последовательности А (х) х( n - k ) на G ( x ) (в нашем случае 1101 1000 110 0000 на 10011).
Табл. 1. Остатки для ℓ -отрезков информационной последовательности
| ℓ- отрезок | Остаток | ℓ- отрезок | Остаток |
|
0000 0001 0010 0011 0100 0101 0110 К-во Просмотров: 250
Бесплатно скачать Лабораторная работа: Программный кодер-декодер для циклических (n,k)-кодов
|