Необходимые сведения из теории

Лабораторная работа

 

"ПРОГРАММНЫЙ КОДЕР-ДЕКОДЕР ДЛЯ ЦИКЛИЧЕСКИХ (n, k) – КОДОВ"

 

 

Преследуемые цели

 

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

- закрепление теоретического материала, касающегося основных положений математической теории линейных (n, k) – кодов;

- осознание механизма кодирования пакетов данных при передаче файлов;

- практическое освоение алгоритмов кодирования и декодирования применительно к циклическим (n, k) – кодам.

 

Необходимые сведения из теории

 

Известно, что циклические коды из всех помехоустойчивых кодов находят наибольшее применение на практике.

Циклические коды представляют собой подкласс (подмножество) линейных (n, k) – кодов. Это значит, что все положения теории, которые справедливы для нециклических линейных (n, k) – кодов, справедливы и для кодов циклических. Но циклические коды обладают рядом дополнительных положительных свойств, в частности, они «остро реагируют» на близко расположенные в кодовом слове ошибки, так называемые «пачки ошибок». Кроме того, для них найдены чрезвычайно простые алгоритмы кодирования и декодирования. Все это и обеспечило им широкое применение на практике. Их применение оговорено многими международными стандартами, регламентирующими работу каналов передачи.

Для описания циклических кодов параллельно используется представление кодовых слов и двоичным вектором, и многочленом от некоторой формальной переменной x. Постоянно приходится переходить от одной формы представления к другой. Одну и ту же двоичную последовательность обозначим V, если она рассматривается как вектор, или V (x), если она интерпретируется как многочлен.

 

Конструктивное определение циклического (n, k) – кода

 

Циклическим (n, k) – кодом называется множество многочленов степени не больше (n ‑1), каждый из которых нацело делится на (специально подобранный) порождающий многочлен G (x) степени (n - k), являющийся делителем бинома xⁿ +1.

Циклический код со словами длины n и с порождающим многочленом G (x) существует тогда и только тогда, когда G (x) делит xⁿ+1 [1]. В лекционном курсе было показано, что это требование делимости бинома xⁿ+1 на G (x) вытекает из специфики определения операции символического умножения многочленов (по модулю бинома xⁿ+1). Для того, чтобы максимизировать множество слов порождаемого кода при фиксированных значениях длины слов n и кодового расстояния d₀, многочлен G (x) должен быть неприводимым делителем степени (n-k).

 

Алгоритм кодирования

 

На практике чаще всего применяется алгоритм кодирования, который формирует систематический разделимый код. В основу такого алгоритма положена операция деления на G (x). Систематические разделимые коды привлекательны тем, что процедуру кодирования, т.е. преобразования информационного вектора A (длины k) в вектор кода V (длины n>k) удается свести лишь к формированию (n-k) контрольных бит.

Шаг 1.   Предварительно вектор A «отнормируем по формату» под длину n, воспользовавшись операцией умножения многочленов A (x) × x^n-k. Как было показано в лекционном курсе – это эквивалентно сдвигу вектора A на (n-k) позиций влево. Произведение многочленов на языке векторов имеет длину n. Существенно для последующего, что правые (n-k) позиций оказываются непременно нулевыми.

Шаг 2.   Произведение A (x) × x^{n - k} разделим на G (x). Ясно, что в общем случае оно не обязано делиться на G (x) нацело. Поэтому следует записать

A (x) × x^n-k= Q (x) × G (x)+ R (x),

 

где Q (x) - частное от деления;

R (x) - остаток. Это многочлен степени не больше (n - k ‑1), т. к. делитель имеет степень (n - k) по определению. Как вектор он имеет длину (n - k).

Шаг 3.   Перенесём остаток R (x) в левую часть равенства. Получим:

A (x) × x^n-k+ R (x)= Q (x) × G (x).

 

Теперь в левой части мы получаем многочлен, который нацело делится на G (x), а это по определению – многочлен, принадлежащий циклическому (n, k) – коду. В этой последней операции остаток R складывается с нулями (см. шаг1 алгоритма). Следовательно, конечный итог эквивалентен конкатенированию R к вектору А.

 

Алгоритм декодирования

 

Известно несколько алгоритмов декодирования циклических (n, k) – кодов. В данной лабораторной работе исследуется «декодирование по синдрому», роль которого (синдрома) играет остаток от деления декодируемого многочлена F (x) на G (x). Декодирование может производиться с целью только обнаруживать ошибки или с целью исправлять ошибки кратности до t включительно. В любом случае цель достигается в несколько шагов алгоритма.

 

Параметры исследуемых кодов

 

Чтобы трудоемкость лабораторных работ согласовать с отпущенным временем, исследуются короткие (по меркам практики) коды. Параметры кодов приведены в таблицах 1 – 3.

Согласуйте с преподавателем номер варианта, с которым Вы будете работать. Программы CODER и DECODER следует писать для одного варианта кода.

 

Таблица №1. Варианты заданий для (n, k) – кодов с длиной слова n=15

Вари-анты	Параметры n, k	Расстояние кода d0	Порождающий многочлен G (x)	G (x) в двоичном и HEX‑форматах
1	2	3	4	5
1.1	(15,11)	3	G 1(x)=x^4+x+1	1 0011«13h
1.2	(15,7)	5	G 2(x)=x^8+x^7+x^6+x^4+1	1 1101 0001«1D1h
1.3	(15,5)	7	G 3(x)=x^10+x^8+x^5+x^4+x^2+x+1	101 0011 0111«537h

 

Таблица №2. Варианты заданий для (n, k) – кодов с длиной слова n=31

Вари-анты	Параметры n, k	Расстояние кода d0	Порождающий многочлен G (x)	G(x) в двоичном и HEX‑форматах
1	2	3	4	5
2.1	(31,26)	3	G 1(x)=x^5+x^2+1	10 0101«25h
2.2			G 2(x)=x^5+x^4+x^2+x+1	11 0111«37h
2.3			G 3(x)=x^5+x^4+x^3+x+1	11 1011«3Bh
2.4			G 4(x)=x^5+x^3+1	10 1001«29h
2.5	(31,21)	5	G 5(x)=x^10+x^9+x^8+x^6+x^5+x^3+1	111 0110 1001«769h
2.6			G 6(x)=x^10+x^7+x^5+x^4+x^2+x+1	100 1011 0111«4B7h
2.7	(31,16)	7	G 7(x)=x^15+x^11+x^10+x^9+x^8+x^7++x^5+ +x^3+x^2+x+1	1000 1111 1010 1111«8FAFh
2.8			G 8(x)=x^15+x^14+x^13+x^12+x^11+ +x^10+x^9+x^8+x^7+x^6+1	1111 1111 1100 0001«FFC1h

Таблица №3. Варианты заданий для (n, k) – кодов с длиной слова n=63

Вари-анты	Параметры n, k	Расстояние кода d0	Порождающий многочлен G (x)	G (x) в двоичном и HEX‑форматах
1	2	3	4	5
3.1	(63,57)	3	G1 (x)= x^6+x+1	100 0011«43h
3.2	(63,51)	5	G 2(x)=Ååх^i, i=12,10,8,5,4,3,0	1 0101 0011 1001«1539h
3.3	(63,45)	7	G 3(x)=Ååх^i, i=18,17,16,15,9,7,6,3,2,1,0	111 1000 0010 1100 1111««782СFh
3.4	(63,39)	9	G 4(x)=Ååх^i, i=24,23,22,20,19,17,16,13, 10,9,8,6,5,4,2,1,0	1 1101 1011 0010 0111 0111 0111««1DB2777h
3.5	(63,36)	11	G 5(x)=Ååх^i, i=27,22,21,19,18,17,15, 8,4,1,0	1 000 0110 1110 1000 0001 0001 0011«86Е8113h
3.6	(63,30)	13	G 6(x)=Ååх^i, i=33,32,30,29,28,27,26,23,22, 20,15,14,13,11,9,8,6,5,1,0	11 0111 1100 1101 0000 1110 1011 0110 0011««37СD0EB63h
3.7	(63,24)	15	G 7(x)=Ååх^i, i=39,38,37,36,34,33,31,28,27, 25,22,19,17,11,6,3,0	111 1011 0100 1101 0010 0101 0000 0100 0100 1001 ««7B4D250449h

 

Алгоритм деления по частям

 

Разобьем k ‑битовую последовательность А, выраженную многочленом А (х), на ℓ‑ битовые отрезки (блоки). Так как в общем случае k не обязано быть кратным ℓ, входная последовательность будет поделена на s блоков, из которых последний имеет длину m ₀ <ℓ. Выполняется условие: k =ℓ (s ‑1)+ m ₀.

Шаг 1

Выделим в последовательности А левые ℓ бит. Пусть в символике многочленов они выражаются многочленом А ₁(х), а оставшуюся (справа) часть обозначим А `₁(х).

Тогда входную последовательность А (х) можно представить в форме:

А (х)= А ₁(х) х^(k-ℓ) + А `₁(х).                                           (1)

 

(Здесь и далее суммирование двоичных многочленов и векторов ведется по mod2).

Делимое А (х) х^(n-k) в алгоритме кодирования запишем как

А (х) х^(n-k) =(А ₁(х) х^(k-ℓ) + А `₁(х)) х^(n-k)                                   (2)

 

Векторная иллюстрация к шагу 1.

При ℓ =4, k =11 (одиннадцать) пусть А =1101 1000 110. Здесь m ₀ =3, А ₁ =1101.

А ₁ (х) х^(k-ℓ) в векторной форме выглядит как 1101 0000000, так как умножение на х^(k-ℓ) эквивалентно приписыванию справа (k - ℓ) нулей. А `<sub>1</sub> =1000 110. Сумма А <sub>1</sub>(х) х<sup>(k-ℓ)</sup> + А `₁ = А(х) выглядит как

1101 0000000

1000110 ^Å

1101 1000110

В выражении (2) первый член суммы в круглых скобках умножим и разделим на порождающий многочлен и произведем умножение обоих членов на х^(n-k). Получим:

 

                     (3)

 

Дробь  представим как меньшую целую часть (частное) Q ₁ (х), которое в конечном итоге нас не интересует, плюс остаток от деления R ₁ (х). С учетом этого перепишем (3).

Получим:

А (х) х^(n-k) = Q ₁ (х) G (x) х^(k-ℓ) + R ₁ (x) х^(k-ℓ) + А `₁ (х) х^(n-k)                     (4)

 

Старшая степень многочлена  не превосходит (ℓ-1), т. к. такую степень по соглашению имеет А ₁(х), а G (x) имеет фиксированную степень (n-k) по определению (вывернутые полускобки символизируют ближайшее меньшее целое от дроби, т.е. частное). Тогда получается, что первое слагаемое в (4) имеет старшую возможную степень (n‑1), что соответствует вектору длины n.

Старшая степень остатка R ₁(x) не превосходит величины (n-k‑1), а всего второго слагаемого в (4) – величины (n-ℓ-1). Такую же степень имеет и третье слагаемое А `₁ (х) х^(n-k). Сложим эти два последних члена, сумму обозначим F ₁(х). Перепишем (4) в следующем виде:

А (х) х^(n-k) = Q ₁ (х) G (x) х^(k-ℓ) + F ₁(х)                             (5)

 

Рис. 1 иллюстрирует формирование последовательности F ₁ в векторной интерпретации всех участвующих величин. Обратим внимание на длину последовательности F ₁, на то обстоятельство, что при суммировании векторы R ₁ и A `₁ «выровнены» со стороны старших разрядов, а F ₁ имеет справа (n-k) нулевых бит.

 

Рис. 1. Формирование последовательности F ₁ при векторном представлении величин

На этом первый шаг алгоритма деления по частям закончен. Получен F ₁(х), куда вошел первый промежуточный остаток R ₁(x), контролирующий деление первого блока из ℓ левых бит входной последовательности А (х).

Шаг 2

Очередной шаг алгоритма заключается в том, что в F ₁(х) выделяем ℓ левых бит. Этот отрезок должен быть обозначен А ₂(х). Оставшаяся правая часть F ₁(х) – это А `₂(х). В соответствии с (3), (4) находим выражение остатка R ₂(x) и последовательности F ₂(х).

 

Рис. 2. Формирование последовательности F ₂ при векторном представлении величин

 

На рис. 2 проиллюстрировано получение F ₂. Предпринята попытка масштабно отобразить изменение участвующих в деле векторов. Здесь показано, что после второго шага F ₂ все еще имеет справа (n-k) нулей. Это эквивалентно допущению, что деление входного вектора А на отрезки длины ℓ двумя шагами не исчерпывается.

Делимое (в его стартовом понимании) после второго шага имеет вид:

 

                                (6)

 

В общем случае, пока (k-iℓ)≥(n-k) вектор F _i должен будет иметь справа (n-k) нулей. Это, как известно, место контрольных бит в словах циклического кодового слова. Они пока не сформированы.

Шаг s‑1

В процессе выполнения (s ‑1) – го шага мы оперируем векторами длины (n - k + m ₀) (см. рис. 3). К этому времени все отрезки длины ℓ в составе входного вектора будут исчерпаны и (если в общем случае k не делится нацело на ℓ) у нас остаётся от входной последовательности вычисленный остаток R _{s -1} и «правый» отрезок A `_s-1 длины m₀<ℓ.

В соответствии с выражениями (4) и (5) получим «выходной продукт» данного шага – многочлен F _{s -1} (х) = R _{s -1} (x) x ^{( k -( s -1)ℓ)} + A ` <sub>s -1</sub> (х) х<sup>( n - k )</sup> = R <sub>s -1</sub> (x) x <sup>( m 0)</sup> + A ` _{s -1} (х) х^{( n - k )}, т. к. k =(s ‑1)ℓ+ m ₀ по определению этих величин.

 

Рис. 3. Формирование последовательности F _{s -1} при векторном представлении величин

 

Обозначим последние формирующиеся (n-k) бит Y (х). Как мы видели до (s‑1) – го шага Y (х)=0. Следовательно, Y (х) можно ввести в (6) как нулевое слагаемое, если пределы суммирования ограничить величиной (s-u‑1). После шага s можно записать

 

                     (7)

 

Здесь  т.е. является проверочными битами кодового слова.

Алгоритм кодирования

 

Известно на старте:

– длина выходных кодовых слов n;

– длина входной последовательности k;

– число контрольных бит (n-k)=r;

– порождающий многочлен G (x);

Назначается величина ℓ≤ r. Вычисляются параметры s и m₀. В памяти машины организуется 2 ^ℓ строк («мест»). В каждую строку для каждой конфигурации двоичного отрезка длины ℓ пишется остаток, вычисленный заранее по изложенному выше алгоритму. В процессе кодирования процедура деления заменяется считыванием из памяти остатка для очередного ℓ -отрезка кодируемой последовательности. Это существенно повышает быстродействие программного кодера при (обычно) приемлемом расходе памяти. Желательно так писать программу, чтобы ℓ -отрезок мог выступать в роли «смещения» по адресному пространству списка остатков.

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

1. Из исходной k‑ битовой информационной последовательности со стороны левых («старших») разрядов выделяется отрезок длины ℓ и из таблицы выбирается соответствующий ему остаток.

2. Полученный остаток суммируется по mod2 с левыми разрядами оставшейся части блока длиной (k-ℓ) бит.

3. Из полученной суммы со стороны левых разрядов выделяется очередной ℓ -отрезок, для которого из таблицы считывается соответствующий остаток и т.д.

4. Через (s‑1) таких шагов из полученной суммы выделяются m₀ старших разрядов ℓ-m₀ и для сформированной ℓ- разрядной комбинации выбирается соответствующий остаток из таблицы.

5. Полученный остаток суммируется по mod 2 с оставшимися (после выделения m₀ разрядов) битами. Эта сумма является комбинацией проверочных разрядов циклического кода.

 

8. Содержательный пример [3]

 

Методом деления по частям построить кодер для циклического (15,11) – кода, заданного порождающим многочленом G (x)=х⁴+х+1.

Здесь n =15; k =11. Выбираем ℓ =4. Тогда s =3, m₀ =3. Всего имеем 2 ^ℓ различных конфигураций ℓ -отрезков. Остатки, соответствующие этим отрезкам, вычисленные в соответствии с алгоритмом деления по частям, приведены в табл. 1.

Пусть входная (информационная) последовательность, разделенная на отрезки, имеет вид: 1101 1000 110

Выбираем первый ℓ -отрезок 1101 и выбираем из таблицы соответствующий остаток 0100. Складываем по mod 2 со следующим отрезком 0100+1000=1100. Полученной сумме соответствует остаток 0111. Поскольку сделано уже (s‑1) шагов, прибавим этот остаток к оставшимся трем битам 0111+110=1011. На этот результат понадобится ссылка, поэтому присвоим ему наименование U _s-1. Из полученной суммы выделим m₀ левых бит и дополним их слева нулями до размерности ℓ (в данном случае – одним нулем). Получим 0101. Из таблицы найдем остаток – 1111. Выполняется s ‑й шаг деления. Оставшуюся «1» (справа) от U _s-1, из которого выделяли m₀ левых бит, сложим со стороны старших разрядов с только – что полученным остатком 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, k) – КОДОВ"

 

 

Преследуемые цели

 

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

- закрепление теоретического материала, касающегося основных положений математической теории линейных (n, k) – кодов;

- осознание механизма кодирования пакетов данных при передаче файлов;

- практическое освоение алгоритмов кодирования и декодирования применительно к циклическим (n, k) – кодам.

 

Необходимые сведения из теории

 

Известно, что циклические коды из всех помехоустойчивых кодов находят наибольшее применение на практике.

Циклические коды представляют собой подкласс (подмножество) линейных (n, k) – кодов. Это значит, что все положения теории, которые справедливы для нециклических линейных (n, k) – кодов, справедливы и для кодов циклических. Но циклические коды обладают рядом дополнительных положительных свойств, в частности, они «остро реагируют» на близко расположенные в кодовом слове ошибки, так называемые «пачки ошибок». Кроме того, для них найдены чрезвычайно простые алгоритмы кодирования и декодирования. Все это и обеспечило им широкое применение на практике. Их применение оговорено многими международными стандартами, регламентирующими работу каналов передачи.

Для описания циклических кодов параллельно используется представление кодовых слов и двоичным вектором, и многочленом от некоторой формальной переменной x. Постоянно приходится переходить от одной формы представления к другой. Одну и ту же двоичную последовательность обозначим V, если она рассматривается как вектор, или V (x), если она интерпретируется как многочлен.