Конечной задачей является написание и отладка программы CODER, способной преобразовать предлагаемый файл. Программа должна рассматривать файл (не обязательно двоичный) как последовательность двоичных векторов Аj длины k и преобразовать его в другой файл - файл, состоящий из слов Vj длины n избыточного кода заданных параметров.

Легко просматривается промежуточная, технологическая задача: нужно иметь средства, с помощью которых можно было бы убедить себя и оппонентов в том, что программа CODER выполняет преобразование требуемым образом. Назовем эту программу отладочной.

4.1 Интерфейс отладочной программы

Необходимо иметь (хотя бы) два «окна»:

одно для ввода вручную кодируемого вектора Аj заданных параметров;

другое - для показа выходного вектора Vj (или только контрольных бит этого вектора).

Необходимо заранее вручную вычислить несколько выходных векторов Vj, соответствующих известным Аj. У преподавателя должны быть заготовлены свои тестовые слова кода. Таким образом можно будет обеспечить определенный уровень доверия к кодирующей программе Вообще говоря, такой метод тестирования большого доверия не заслуживает не только из-за малого числа проверяемых векторов, но и из-за кодирования входных векторов «порознь», а не путем их «извлечения» из файла произвольного формата. На вспомогательных операциях легко привнести ошибку в кодирование. Однако, из-за ограниченности времени таким поверхностным тестированием придется удовлетвориться.

Можно написать исходный файл известной двоичной структуры и искать несложные приемы просмотра двоичной структуры выходного файла, структура которого тоже становится наперед известной..

4.2 Интерфейс основной кодирующей программы CODER Интерфейсы основной и вспомогательной программ, разумеется, могут быть совмещены.

Необходимо предусмотреть возможность выбора исходного (кодируемого) файла из каталогов Windows (или писать вручную в какой-либо «командной строке» путь к этому файлу). Необходимо предусмотреть возможность запоминания выходного файла программы CODER на диске и возможность многократного возвращения к анализу этого файла.

Выходной файл (файлы) программы CODER понадобятся при выполнении лабораторной работы, связанной с декодированием.

4.3 Отчет по лабораторной работе, защита результатов

Отчет должен содержать:

краткое изложение постановки задачи;

требуемые параметры выходного кода и граф-схему алгоритма работы основного кодирующего модуля с комментариями;

характер и результаты тестового кодирования:

(5…6) «пар» входных и выходных векторов кодера;

проверка свойства замкнутости множества кодовых векторов относительно операции суммирования по mod2;

проверка расстояний между кодовыми векторами на соответствие исходным требованиям.

Результаты работы программы CODER должны быть продемонстрированы преподавателю.

5. Условия и порядок выполнения лабораторной работы DECODER

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

Исходными данными, предметом преобразований для программы DECODER должен явиться выходной файл программы CODER. Но как и в лабораторной работе CODER, здесь также понадобится определенная технология отладки основного модуля, с помощью которой можно убедиться в правильности работы программы DECODER и проанализировать спецификации обнаруживаемых / исправляемых ошибок.

5.1 Интерфейс отладочного модуля

Интерфейс может быть построен по принципу двух окон - «входное» и «выходное». Необходимо иметь возможность вручную вводить декодируемую двоичную последовательность (неискаженное слово кода, искаженное слово, вектор ошибки) и получать в выходном окне результат декодирования (вид синдрома Но не значение типа «ноль/не ноль» без раскрытия структуры синдрома., структуру вычисленной (предполагаемой) ошибки или исправленное слово кода, в зависимости от конкретного варианта задания и Вашего решения).

5.2 Элементарный план отладки декодирующего модуля

Взять 3-4 вектора кода V1, V2, V3, V4 и убедиться, что они дают нулевой остаток;

Подействовать на эти векторы ошибками.

Имея в виду, что искажение многочлена Vj(х) моделируется операцией Fj?(х)=Vj(х)+E?(х), где многочлен E?(х) символизирует ?-тую конфигурацию ошибок, результат вычисления синдрома (остатка) Rj?(x)=Fj?(х)/G(x) можно представить как R?(x)=E?(х)/G(x) V(х) по определению нацело делится на G(x). Следовательно, при правильном функционировании программы DECODER должны получиться остатки, подчиняющиеся следующей схеме (табл. 4).

Таблица 4

Если поведение DECODER`а подчиняется таблице 4, его можно принять для дальнейшей работы в соответствии с индивидуальным заданием.

5.3 Вариант DECODER`а с обнаружением ошибок

Исходя из характеристик G(x) и величины d0, предложить конфигурации ошибок, которые программа непременно должна обнаруживать и которые не обязана обнаруживать. Особое внимание следует обратить на конфигурации ошибок типа «пачка», вес которых находится в пределах (n-k)w(E)(d0-1).

Найти конфигурации необнаруживаемых ошибок, сформулировать свойства (признаки) таких ошибок;

Результаты исследования свести в таблицу и снабдить комментариями.

5.4 Вариант DECODER`а с исправлением ошибок

Исходя из характеристик G(x) и величины d0, предложить конфигурации ошибок, которые иллюстрируют свойства кода в отношении исправления ошибок. Подобрать конфигурации, ведущие к «неправильному исправлению», т.е. к вручению получателю кодового слова с незамеченными ошибками, которые остаются после формально выполненной процедуры исправления.

6. Защита результатов, отчет по лабораторной работе

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

7. Быстрый кодер / декодер для циклических кодов

Применение быстрого алгоритма в лабораторной работе не является обязательным для всех. Он может быть использован по желанию студентов или по прямому указанию преподавателя.

Выше говорилось, что при циклическом кодировании основной операцией алгоритмов кодирования входной последовательности А(х) и декодирования выходной является операция деления выражения А(х) х(n-k) на порождающий многочлен с целью нахождения остатка, который суммируется с А(х) х(n-k) по mod2.

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

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

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

А(х) х(n-k) =Q1(х) G(x) х(k-?) +F1(х) (5)

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

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

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

Шаг 2

Очередной шаг алгоритма заключается в том, что в F1(х) выделяем ? левых бит. Этот отрезок должен быть обозначен А2(х). Оставшаяся правая часть F1(х) - это А`2(х). В соответствии с (3), (4) находим выражение остатка R2(x) и последовательности F2(х).

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

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

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

(6)

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

Шаг s_1

В процессе выполнения (s_1) - го шага мы оперируем векторами длины (n-k+m0) (см. рис. 3). К этому времени все отрезки длины ? в составе входного вектора будут исчерпаны и (если в общем случае k не делится нацело на ?) у нас остаётся от входной последовательности вычисленный остаток Rs-1 и «правый» отрезок A`s-1 длины m0<?.

В соответствии с выражениями (4) и (5) получим «выходной продукт» данного шага - многочлен Fs-1(х) = Rs-1(x) x(k-(s-1)?) + A`s-1 (х) х(n-k) =Rs-1(x) x(m0) + A`s-1 (х) х(n-k), т. к. k=(s_1)?+m0 по определению этих величин.

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

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

(7)

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

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

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

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

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

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

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

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

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

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

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

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

Через (s_1) таких шагов из полученной суммы выделяются m0 старших разрядов ?-m0 и для сформированной ?-разрядной комбинации выбирается соответствующий остаток из таблицы.

Полученный остаток суммируется по 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. На этот результат понадобится ссылка, поэтому присвоим ему наименование s-1. Из полученной суммы выделим m0 левых бит и дополним их слева нулями до размерности ? (в данном случае - одним нулем). Получим 0101. Из таблицы найдем остаток - 1111. Выполняется s_й шаг деления. Оставшуюся «1» (справа) от s-1, из которого выделяли m0 левых бит, сложим со стороны старших разрядов с только - что полученным остатком 1111+1=0111. Это и есть контрольные биты к информационной последовательности 1101 1000 110.

Результат можно проверить традиционным делением последовательности А(х) х(n-k) на G(x) (в нашем случае 1101 1000 110 0000 на 10011).

Табл. 1. Остатки для ?-отрезков информационной последовательности

Использованная литература

1. М.Н. Аршинов, Л.Е. Садовский Коды и математика (рассказы о кодировании).-М.: Наука, Главная редакция физико-математической литературы, 1983. - 144 с.

2. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. _ М.: Мир, 1986. - 576 с.

3. Гончаров Е.А, Слепаков В.Б. Об одном методе кодирования информации циклическими кодами на универсальной ЭВМ. - В кн.: Сб научных трудов ЦНИИС. М., 1970, вып. 3, с. 58-65.

4. В.С. Чернега, В.А. Василенко, В.Н. Бондарев Расчет и проектирование технических средств обмена и передачи информации: Учебное пособие для вузов. - М.: Высш. шк., 1990. -224 с.

Страницы: 1, 2