Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Конструктивное определение циклического ( 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).
Алгоритм кодирования
На практике чаще всего применяется алгоритм кодирования, который формирует систематический разделимый код. В основу такого алгоритма положена операция деления на 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 к вектору А.
Алгоритм декодирования
Известно несколько алгоритмов декодирования циклических (n, k) – кодов. В данной лабораторной работе исследуется «декодирование по синдрому», роль которого (синдрома) играет остаток от деления декодируемого многочлена F (x) на G (x). Декодирование может производиться с целью только обнаруживать ошибки или с целью исправлять ошибки кратности до t включительно. В любом случае цель достигается в несколько шагов алгоритма.
Декодирование с обнаружением ошибок Шаг 1. Вычисление остатка R (x); Шаг 2. Анализ остатка «на ноль». Нулевой остаток означает, что ошибки не обнаружены;
Декодирование с исправлением ошибок Шаг 1. Вычисление остатка R (x); Шаг 2. Вычисление по найденному остатку предполагаемого (наиболее вероятного) многочлена ошибки Е (х); Шаг 3. Исправление декодируемого вектора F путем суммирования F + E = V; Параметры исследуемых кодов
Чтобы трудоемкость лабораторных работ согласовать с отпущенным временем, исследуются короткие (по меркам практики) коды. Параметры кодов приведены в таблицах 1 – 3. Согласуйте с преподавателем номер варианта, с которым Вы будете работать. Программы CODER и DECODER следует писать для одного варианта кода.
Таблица №1. Варианты заданий для (n, k) – кодов с длиной слова n=15
Таблица №2. Варианты заданий для (n, k) – кодов с длиной слова n=31
Таблица №3. Варианты заданий для (n, k) – кодов с длиной слова n=63
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2019-10-15; просмотров: 111; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.145.77.114 (0.006 с.) |