Навигация
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. Полученный остаток суммируется по mod2 с оставшимися (после выделения 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. Складываем по mod2 со следующим отрезком 0100+1000=1100. Полученной сумме соответствует остаток 0111. Поскольку сделано уже (s‑1) шагов, прибавим этот остаток к оставшимся трем битам 0111+110=1011. На этот результат понадобится ссылка, поэтому присвоим ему наименование Us-1. Из полученной суммы выделим m0 левых бит и дополним их слева нулями до размерности ℓ (в данном случае – одним нулем). Получим 0101. Из таблицы найдем остаток – 1111. Выполняется s‑й шаг деления. Оставшуюся «1» (справа) от Us-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 0111 | 0000 0011 0110 0101 1100 1111 1010 1001 | 1000 1001 1010 1011 1100 1101 1110 1111 | 1011 1000 1101 1110 0111 0100 0001 0010 |
Использованная литература
1. М.Н. Аршинов, Л.Е. Садовский Коды и математика (рассказы о кодировании).-М.: Наука, Главная редакция физико-математической литературы, 1983. – 144 с.
2. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. ‑ М.: Мир, 1986. – 576 с.
3. Гончаров Е.А, Слепаков В.Б. Об одном методе кодирования информации циклическими кодами на универсальной ЭВМ. – В кн.: Сб научных трудов ЦНИИС. М., 1970, вып. 3, с. 58–65.
4. В.С. Чернега, В.А. Василенко, В.Н. Бондарев Расчет и проектирование технических средств обмена и передачи информации: Учебное пособие для вузов. – М.: Высш. шк., 1990. –224 с.
[1] Здесь и всюду далее операции суммирования выполняются по mod2.
[2] Вообще говоря, такой метод тестирования большого доверия не заслуживает не только из-за малого числа проверяемых векторов, но и из-за кодирования входных векторов «порознь», а не путем их «извлечения» из файла произвольного формата. На вспомогательных операциях легко привнести ошибку в кодирование. Однако, из-за ограниченности времени таким поверхностным тестированием придется удовлетвориться.
Можно написать исходный файл известной двоичной структуры и искать несложные приемы просмотра двоичной структуры выходного файла, структура которого тоже становится наперед известной.
[3] Интерфейсы основной и вспомогательной программ, разумеется, могут быть совмещены.
[4] Но не значение типа «ноль/не ноль» без раскрытия структуры синдрома.
[5] V(х) по определению нацело делится на G(x).
Похожие работы
... , если его длина n=qm-1 над GF(q). Если длина кода меньше длины примитивного кода, то код называется укороченным или непримитивным. Общее свойство кодовых слов циклического кода - это их делимость без остатка на некоторый многочлен g(x), называемый порождающим. Результатом деления двучлена xn+1 на многочлен g(x) является проверочный многочлен h(x). При декодировании циклических кодов используются ...
... также невысока и обычно составляет около 100 кбайт/с. НКМЛ могут использовать локальные интерфейсы SCSI. Лекция 3. Программное обеспечение ПЭВМ 3.1 Общая характеристика и состав программного обеспечения 3.1.1 Состав и назначение программного обеспечения Процесс взаимодействия человека с компьютером организуется устройством управления в соответствии с той программой, которую пользователь ...
... информация должна поступать в декодер при восстановлении звукового сигнала. Декодер преобразует серию сжатых мгновенных спектров сигнала в обычную цифровую волновую форму. Audio MPEG - группа методов сжатия звука, стандартизованная MPEG (Moving Pictures Experts Group - экспертной группой по обработке движущихся изображений). Методы Audio MPEG существуют в виде нескольких типов - MPEG-1, MPEG-2 и ...
... приложении 1. Кодер позволяет получить контрольные символы по информационным. Схема составлена в полном соответствии с выражениями (9) и матрицей (10). Декодер соответствует матрице (11). В приложении 2 приведена схема всей системы передачи данных. Исходный код (11 байт) подаётся на регистр REG1. Это можно сделать, например, трёхкратной передачей по 32 разряда (4 байта). Регистр может быть также ...
0 комментариев