Программный кодер-декодер для циклических (n,k)-кодов (стр. 2 из 3)
- одно для ввода вручную кодируемого вектора Аjзаданных параметров;
- другое – для показа выходного вектора Vj (или только контрольных бит этого вектора).
Необходимо заранее вручную вычислить несколько выходных векторов Vj, соответствующих известным Аj. У преподавателя должны быть заготовлены свои тестовые слова кода. Таким образом можно будет обеспечить определенный уровень доверия к кодирующей программе[2].
4.2 Интерфейс основной кодирующей программы CODER[3]
Необходимо предусмотреть возможность выбора исходного (кодируемого) файла из каталогов Windows (или писать вручную в какой-либо «командной строке» путь к этому файлу). Необходимо предусмотреть возможность запоминания выходного файла программы CODER на диске и возможность многократного возвращения к анализу этого файла.
Выходной файл (файлы) программы CODER понадобятся при выполнении лабораторной работы, связанной с декодированием.
4.3 Отчет по лабораторной работе, защита результатов
Отчет должен содержать:
- краткое изложение постановки задачи;
- требуемые параметры выходного кода и граф-схему алгоритма работы основного кодирующего модуля с комментариями;
- характер и результаты тестового кодирования:
· (5…6) «пар» входных и выходных векторов кодера;
· проверка свойства замкнутости множества кодовых векторов относительно операции суммирования по mod2;
· проверка расстояний между кодовыми векторами на соответствие исходным требованиям.
Результаты работы программы CODER должны быть продемонстрированы преподавателю.
5. Условия и порядок выполнения лабораторной работы DECODER
Конечной задачей в данной работе является не только практическое изучение алгоритма декодирования по синдрому (остатку) и отладка декодирующей программы, но и изучение структуры (конфигураций) обнаруживаемых и / или исправляемых ошибок, т.е. косвенная оценка помехоустойчивости кода с конкретными заданными параметрами. Программа – DECODER должна уметь декодировать предлагаемый файл.
Исходными данными, предметом преобразований для программы DECODER должен явиться выходной файл программы CODER. Но как и в лабораторной работе CODER, здесь также понадобится определенная технология отладки основного модуля, с помощью которой можно убедиться в правильности работы программы DECODER и проанализировать спецификации обнаруживаемых / исправляемых ошибок.
5.1 Интерфейс отладочного модуля
Интерфейс может быть построен по принципу двух окон – «входное» и «выходное». Необходимо иметь возможность вручную вводить декодируемую двоичную последовательность (неискаженное слово кода, искаженное слово, вектор ошибки) и получать в выходном окне результат декодирования (вид синдрома[4], структуру вычисленной (предполагаемой) ошибки или исправленное слово кода, в зависимости от конкретного варианта задания и Вашего решения).
5.2 Элементарный план отладки декодирующего модуля
1) Взять 3–4 вектора кода V1, V2, V3,V4 и убедиться, что они дают нулевой остаток;
2) Подействовать на эти векторы ошибками.
Имея в виду, что искажение многочлена Vj(х) моделируется операцией Fjℓ(х)=Vj(х)+Eℓ(х), где многочлен Eℓ(х) символизирует ℓ-тую конфигурацию ошибок, результат вычисления синдрома (остатка) Rjℓ(x)=Fjℓ(х)/G(x) можно представить как Rℓ(x)=Eℓ(х)/G(x)[5] Следовательно, при правильном функционировании программы DECODER должны получиться остатки, подчиняющиеся следующей схеме (табл. 4).
Таблица 4
| E1 | Rℓ | E2 | Rm | |
| Vi | Fi1(х)=Vi(х)+E1(х) | R1 | Fi2(х)=Vi(х)+E2(х) | R2 |
| Vj | Fj1(х)=Vj(х)+E1(х) | R1 | Fj2(х)=Vj(х)+E2(х) | R2 |
Если поведение 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.
Трудность программной реализации кодирующих и декодирующих модулей для циклических кодов состоит в том, что алгоритмы, обычно, предусматривают процедуру многократно повторяемого «битового деления». Время кодирования /декодирования часто оказывается неприемлемым. Далее излагается математическая суть алгоритма деления двоичных последовательностей, позволяющего выполнять деление по частям. «Крупностью» частей в известных пределах можно варьировать, добиваясь оптимизации процедуры в конкретных условиях.
7.1 Алгоритм деления по частям
Разобьем k‑битовую последовательность А, выраженную многочленом А(х), на ℓ‑битовые отрезки (блоки). Так как в общем случае k не обязано быть кратным ℓ, входная последовательность будет поделена на s блоков, из которых последний имеет длину m0<ℓ. Выполняется условие: k=ℓ (s‑1)+m0.
Шаг 1
Выделим в последовательности А левые ℓ бит. Пусть в символике многочленов они выражаются многочленом А1(х), а оставшуюся (справа) часть обозначим А`1(х).
Тогда входную последовательность А(х) можно представить в форме:
А(х)=А1(х) х(k-ℓ) +А`1(х). (1)
(Здесь и далее суммирование двоичных многочленов и векторов ведется по mod2).
Делимое А(х) х(n-k) в алгоритме кодирования запишем как
А(х) х(n-k) =(А1(х) х(k-ℓ) +А`1(х)) х(n-k) (2)
Векторная иллюстрация к шагу 1.
При ℓ=4, k=11 (одиннадцать) пусть А=1101 1000 110. Здесь m0=3, А1=1101.
А1(х) х(k-ℓ) в векторной форме выглядит как 1101 0000000, так как умножение на х(k-ℓ) эквивалентно приписыванию справа (k-ℓ) нулей. А`1=1000 110. Сумма А1(х) х(k-ℓ) +А`1 =А(х) выглядит как
1101 0000000
1000110 Å
1101 1000110
В выражении (2) первый член суммы в круглых скобках умножим и разделим на порождающий многочлен и произведем умножение обоих членов на х(n-k). Получим:
(3)Дробь
представим как меньшую целую часть (частное) Q1(х), которое в конечном итоге нас не интересует, плюс остаток от деления R1(х). С учетом этого перепишем (3).Получим:
А(х) х(n-k) =Q1(х) G(x) х(k-ℓ) +R1(x) х(k-ℓ)+А`1(х) х(n-k) (4)
Старшая степень многочлена
не превосходит (ℓ-1), т. к. такую степень по соглашению имеет А1(х), а G(x) имеет фиксированную степень (n-k) по определению (вывернутые полускобки символизируют ближайшее меньшее целое от дроби, т.е. частное). Тогда получается, что первое слагаемое в (4) имеет старшую возможную степень (n‑1), что соответствует вектору длины n.