Реферат на тему "Программный кодер декодер для циклических n k кодов"




Реферат на тему

текст обсуждение файлы править категориядобавить материалпродать работу




Лабораторная работа на тему Программный кодер декодер для циклических n k кодов

скачать

Найти другие подобные рефераты.

Лабораторная работа *
Размер: 92.82 кб.
Язык: русский
Разместил (а): Maddy1990
1 2 Следующая страница

добавить материал

Кафедра Автоматики и Информационных Технологий
Лабораторная работа
"ПРОГРАММНЫЙ КОДЕР-ДЕКОДЕР ДЛЯ ЦИКЛИЧЕСКИХ (n, k) – КОДОВ"

1.                 Преследуемые цели
Проведение лабораторных работ по данной тематике преследует следующие цели:
-          закрепление теоретического материала, касающегося основных положений математической теории линейных (n, k) – кодов;
-          осознание механизма кодирования пакетов данных при передаче файлов;
-          практическое освоение алгоритмов кодирования и декодирования применительно к циклическим (n, k) – кодам.

2.                 Необходимые сведения из теории
Известно, что циклические коды из всех помехоустойчивых кодов находят наибольшее применение на практике.
Циклические коды представляют собой подкласс (подмножество) линейных (n, k) – кодов. Это значит, что все положения теории, которые справедливы для нециклических линейных (n, k) – кодов, справедливы и для кодов циклических. Но циклические коды обладают рядом дополнительных положительных свойств, в частности, они «остро реагируют» на близко расположенные в кодовом слове ошибки, так называемые «пачки ошибок». Кроме того, для них найдены чрезвычайно простые алгоритмы кодирования и декодирования. Все это и обеспечило им широкое применение на практике. Их применение оговорено многими международными стандартами, регламентирующими работу каналов передачи.
Для описания циклических кодов параллельно используется представление кодовых слов и двоичным вектором, и многочленом от некоторой формальной переменной x. Постоянно приходится переходить от одной формы представления к другой. Одну и ту же двоичную последовательность обозначим V, если она рассматривается как вектор, или V(x), если она интерпретируется как многочлен.
2.1 Конструктивное определение циклического (n, k) – кода
Циклическим (n, k) – кодом называется множество многочленов степени не больше (n‑1), каждый из которых нацело делится на (специально подобранный) порождающий многочлен G(x) степени (n-k), являющийся делителем бинома xn+1.
Циклический код со словами длины n и с порождающим многочленом G(x) существует тогда и только тогда, когда G(x) делит xn+1[1]. В лекционном курсе было показано, что это требование делимости бинома xn+1 на G(x) вытекает из специфики определения операции символического умножения многочленов (по модулю бинома xn+1). Для того, чтобы максимизировать множество слов порождаемого кода при фиксированных значениях длины слов n и кодового расстояния d0, многочлен G(x) должен быть неприводимым делителем степени (n-k).
2.2 Алгоритм кодирования
На практике чаще всего применяется алгоритм кодирования, который формирует систематический разделимый код. В основу такого алгоритма положена операция деления на G(x). Систематические разделимые коды привлекательны тем, что процедуру кодирования, т.е. преобразования информационного вектора A (длины k) в вектор кода V (длины n>k) удается свести лишь к формированию (n-k) контрольных бит.
Шаг 1.        Предварительно вектор A «отнормируем по формату» под длину n, воспользовавшись операцией умножения многочленов A(x)×xn-k. Как было показано в лекционном курсе – это эквивалентно сдвигу вектора A на (n-k) позиций влево. Произведение многочленов на языке векторов имеет длину n. Существенно для последующего, что правые (n-k) позиций оказываются непременно нулевыми.
Шаг 2.        Произведение A(x)×xn-k разделим на G(x). Ясно, что в общем случае оно не обязано делиться на G(x) нацело. Поэтому следует записать
A(x)×xn-k=Q(x)×G(x)+R(x),
где     Q(x) - частное от деления;
R(x) - остаток. Это многочлен степени не больше (n-k‑1), т. к. делитель имеет степень (n-k) по определению. Как вектор он имеет длину (n-k).
Шаг 3.        Перенесём остаток R(x) в левую часть равенства. Получим:
A(x)×xn-k+R(x)=Q(x)×G(x).
Теперь в левой части мы получаем многочлен, который нацело делится на G(x), а это по определению – многочлен, принадлежащий циклическому (n, k) – коду. В этой последней операции остаток R складывается с нулями (см. шаг1 алгоритма). Следовательно, конечный итог эквивалентен конкатенированию R к вектору А.
2.3 Алгоритм декодирования
Известно несколько алгоритмов декодирования циклических (n, k) – кодов. В данной лабораторной работе исследуется «декодирование по синдрому», роль которого (синдрома) играет остаток от деления декодируемого многочлена F(x) на G(x). Декодирование может производиться с целью только обнаруживать ошибки или с целью исправлять ошибки кратности до t включительно. В любом случае цель достигается в несколько шагов алгоритма.
2.3.1 Декодирование с обнаружением ошибок
Шаг 1.        Вычисление остатка R(x);
Шаг 2.        Анализ остатка «на ноль». Нулевой остаток означает, что ошибки не обнаружены;
2.3.2 Декодирование с исправлением ошибок
Шаг 1.        Вычисление остатка R(x);
Шаг 2.        Вычисление по найденному остатку предполагаемого (наиболее вероятного) многочлена ошибки Е(х);
Шаг 3.        Исправление декодируемого вектора F путем суммирования F+E=V;

3. Параметры исследуемых кодов
Чтобы трудоемкость лабораторных работ согласовать с отпущенным временем, исследуются короткие (по меркам практики) коды. Параметры кодов приведены в таблицах 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
G1(x)=x4+x+1
1 0011«13h
1.2
(15,7)
5
G2(x)=x8+x7+x6+x4+1
1 1101 0001«1D1h
1.3
(15,5)
7
G3(x)=x10+x8+x5+x4+x2+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
G1(x)=x5+x2+1
10 0101«25h
2.2
G2(x)=x5+x4+x2+x+1
11 0111«37h
2.3
G3(x)=x5+x4+x3+x+1
11 1011«3Bh
2.4
G4(x)=x5+x3+1
10 1001«29h
2.5
(31,21)
5
G5(x)=x10+x9+x8+x6+x5+x3+1
111 0110 1001«769h
2.6
G6(x)=x10+x7+x5+x4+x2+x+1
100 1011 0111«4B7h
2.7
(31,16)
7
G7(x)=x15+x11+x10+x9+x8+x7++x5+
+x3+x2+x+1
1000 1111 1010 1111«8FAFh
2.8
G8(x)=x15+x14+x13+x12+x11+
+x10+x9+x8+x7+x6+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)=x6+x+1
100 0011«43h
3.2
(63,51)
5
G2(x)=Ååхi, i=12,10,8,5,4,3,0
1 0101 0011 1001«1539h
3.3
(63,45)
7
G3(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
G4(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
G5(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
G6(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
G7(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

4. Порядок выполнения лабораторной работы CODER
Конечной задачей является написание и отладка программы CODER, способной преобразовать предлагаемый файл. Программа должна рассматривать файл (не обязательно двоичный) как последовательность двоичных векторов Аj длины k и преобразовать его в другой файл – файл, состоящий из слов Vj длины n избыточного кода заданных параметров.
Легко просматривается промежуточная, технологическая задача: нужно иметь средства, с помощью которых можно было бы убедить себя и оппонентов в том, что программа CODER выполняет преобразование требуемым образом. Назовем эту программу отладочной.
4.1 Интерфейс отладочной программы
Необходимо иметь (хотя бы) два «окна»:
-          одно для ввода вручную кодируемого вектора Аj заданных параметров;
-          другое – для показа выходного вектора Vj (или только контрольных бит этого вектора).
Необходимо заранее вручную вычислить несколько выходных векторов Vj, соответствующих известным Аj. У преподавателя должны быть заготовлены свои тестовые слова кода. Таким образом можно будет обеспечить определенный уровень доверия к кодирующей программе[2].

4.2 Интерфейс основной кодирующей программы CODER[3]
Необходимо предусмотреть возможность выбора исходного (кодируемого) файла из каталогов Windows (или писать вручную в какой-либо «командной строке» путь к этому файлу). Необходимо предусмотреть возможность запоминания выходного файла программы CODER на диске и возможность многократного возвращения к анализу этого файла.
Выходной файл (файлы) программы CODER понадобятся при выполнении лабораторной работы, связанной с декодированием.
4.3 Отчет по лабораторной работе, защита результатов
Отчет должен содержать:
q     краткое изложение постановки задачи;
q     требуемые параметры выходного кода и граф-схему алгоритма работы основного кодирующего модуля с комментариями;
q     характер и результаты тестового кодирования:
·        (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 2 Следующая страница


Программный кодер декодер для циклических n k кодов

Скачать лабораторную работу бесплатно


Постоянный url этой страницы:
http://referatnatemu.com/37119



вверх страницы

Рейтинг@Mail.ru
Copyright © 2010-2015 referatnatemu.com