48287 (566504)
Текст из файла
Кафедра Автоматики и Информационных Технологий
Лабораторная работа
"ПРОГРАММНЫЙ КОДЕР-ДЕКОДЕР ДЛЯ ЦИКЛИЧЕСКИХ (n, k) – КОДОВ"
-
Преследуемые цели
Проведение лабораторных работ по данной тематике преследует следующие цели:
-
закрепление теоретического материала, касающегося основных положений математической теории линейных (n, k) – кодов;
-
осознание механизма кодирования пакетов данных при передаче файлов;
-
практическое освоение алгоритмов кодирования и декодирования применительно к циклическим (n, k) – кодам.
-
Необходимые сведения из теории
Известно, что циклические коды из всех помехоустойчивых кодов находят наибольшее применение на практике.
Циклические коды представляют собой подкласс (подмножество) линейных (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+11. В лекционном курсе было показано, что это требование делимости бинома 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 001113h |
| 1.2 | (15,7) | 5 | G2(x)=x8+x7+x6+x4+1 | 1 1101 00011D1h |
| 1.3 | (15,5) | 7 | G3(x)=x10+x8+x5+x4+x2+x+1 | 101 0011 0111537h |
Таблица №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 010125h |
| 2.2 | G2(x)=x5+x4+x2+x+1 | 11 011137h | ||
| 2.3 | G3(x)=x5+x4+x3+x+1 | 11 10113Bh | ||
| 2.4 | G4(x)=x5+x3+1 | 10 100129h | ||
| 2.5 | (31,21) | 5 | G5(x)=x10+x9+x8+x6+x5+x3+1 | 111 0110 1001769h |
| 2.6 | G6(x)=x10+x7+x5+x4+x2+x+1 | 100 1011 01114B7h | ||
| 2.7 | (31,16) | 7 | G7(x)=x15+x11+x10+x9+x8+x7++x5+ | 1000 1111 1010 11118FAFh |
| 2.8 | G8(x)=x15+x14+x13+x12+x11+ | 1111 1111 1100 0001FFC1h |
Таблица №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 001143h |
| 3.2 | (63,51) | 5 | G2(x)=хi, i=12,10,8,5,4,3,0 | 1 0101 0011 10011539h |
| 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, | 1 1101 1011 0010 0111 0111 0111 1DB2777h |
| 3.5 | (63,36) | 11 | G5(x)=хi, i=27,22,21,19,18,17,15, | 1 000 0110 1110 1000 0001 0001 001186Е8113h |
| 3.6 | (63,30) | 13 | G6(x)=хi, i=33,32,30,29,28,27,26,23,22, | 11 0111 1100 1101 0000 1110 1011 0110 0011 |
| 3.7 | (63,24) | 15 | G7(x)=хi, i=39,38,37,36,34,33,31,28,27, | 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.
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
