Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Федеральное агентство связи
МОСКОВСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ СВЯЗИ И ИНФОРМАТИКИ (МТУСИ)
Кафедра мультимедийных сетей и услуг связи
Лабораторная работа №13
Исследование свойств циклических кодов
Выполнила: Коровкина А.А.
Группа: СС1001
Проверил: Друзь В.В.
МОСКВА
2013
Цель работы:
1. Изучить основные принципы помехоустойчивого кодирования.
2. Изучить правила построения циклических кодов.
3. Исследовать обнаруживающие и исправляющие свойства циклических кодов.
4. Познакомится c принципом построения кодирующих и декодирующих устройств циклических кодов.
Кодер
Источник
Декодер_1
Исправление ошибки
Декодер_2
Обнаружение ошибки
Канал
Источник ошибки
Схема лабораторного макета
Индивидуальное задание:
Дан линейный код типа (7, 4) с образующим полиномом вида Х3+Х+1. Кодовое расстояние d=3
1) Найдем все кодовые слова заданного кода.
Образующий полином определяет кодовую последовательность:
V(x) = 1* x3+ 0*x2 +1*x + 1.
V(x)= 1 0 1 1
Допишем образующую комбинацию до кодового слова:
1 0 1 1 0 0 0
Циклическим сдвигом влево получим еще 6 кодовых слов:
0 1 1 0 0 0 1
1 1 0 0 0 1 0
1 0 0 0 1 0 1
0 0 0 1 0 1 1
0 0 1 0 1 1 0
0 1 0 1 1 0 0
Получили 7 кодовых слов. Поскольку k=4, число кодовых слов равно 2k=16, причем одно из них является комбинацией 0 0 0 0 0 0 0.
Сложением в разных комбинациях найденных кодовых слов по модулю 2 найдем остальные кодовые слова. Например:
1 0 1 1 0 0 0
(+)0 1 1 0 0 0 1
1 1 0 1 0 0 1
Таким образом, получим 16 кодовых слов.
0 0 0 0 0 0 0
1 1 1 1 1 1 1
0 1 1 0 0 0 1
1 1 0 0 0 1 0
1 0 0 0 1 0 1
0 0 0 1 0 1 1
0 0 1 0 1 1 0
0 1 0 1 1 0 0
1 0 1 1 0 0 0
0 1 0 0 1 1 1
1 0 0 1 1 1 0
0 0 1 1 1 0 1
0 1 1 1 0 1 0
1 1 1 0 1 0 0
1 1 0 1 0 0 1
1 0 1 0 0 1 1
2)Характеристики заданного кода в режиме исправления ошибок.
В режиме исправления ошибок декодер вычисляет остаток S(x) от деления принятой последовательности P(x) на g(x). Этот остаток называют синдромом. Принятый полином P(x) представляет собой сумму по модулю два переданного слова V(x) и вектора ошибок E(x):
P(x) = V(x) E(x)к.
Найдем синдромы ошибок.
d≥2t+1
2≥2t => t=1
Кратность ошибок не превышает единицу, значит декодер будет исправлять только одну ошибку в комбинации, значит вектор ошибки будет содержать 1 единицу. Исходя из этого, найдем вектора ошибки.
1 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 1
Рассчитаем синдромы ошибки. Для этого надо разделить комбинацию на выходе канала (суммированую с вектором ошибки) на образующий полином. Допустим, комбинация на входе канала 1 0 1 1 0 0 0, вектор ошибки 1 0 0 0 0 0 0. Комбинация на выходе канала- 0 0 1 1 0 0 0. Разделим на образующий полином 1 0 1 1.
0 0 1 1 0 0 0 | 1 0 1 1
(+) 1 0 1 1
1 1 1 0
(+) 1 0 1 1
1 0 1 <= Остаток и будет синдромом ошибки.
Аналогично найдем остальные синдромы.
1 0 0 0 0 0 0 1 0 1
0 1 0 0 0 0 0 1 1 1
0 0 1 0 0 0 0 1 1 0
0 0 0 1 0 0 0 0 1 1
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0 0 1
Отметим, что один и тот же синдром может соответствовать 2k различным векторам ошибок. Положим, синдром S(x) соответствует вектору ошибок E1(x). Но и все векторы ошибок, равные сумме E1(x) V(x), где V(x) любое кодовое слово, будут давать тот же синдром.
Например: Вектор ошибки 0 0 0 0 1 0 1, с синдромом 1 0 1, таким же, как у вектора ошибки
1 0 0 0 0 0 0. При этом, в первом случае комбинация будет декодирована неправильно. Поэтому, поставив в соответствие синдрому S1(x) вектор ошибок E1(x), мы будем осуществлять правильное декодирование в случае, когда действительно вектор ошибок равен E1(x), во всех остальных 2k-1 случаях декодирование будет ошибочным.
Вероятность ошибочного декодирования будет равна вероятности Pn(>t) появления векторов ошибок веса t + 1 и больше в заданном канале. Для ДСК эта вероятность будет равна
В режиме обнаружения ошибок, если принятая последовательность делится без остатка на g(x), делается вывод, что ошибки нет или она не обнаруживается. В противном случае комбинация бракуется.
d≥σ+1
3≥σ+1 => σ≤2
Кратность гарантированно обнаруживаемых ошибок σ≤2.
Слова любого линейного кода обладают свойством замкнутости по отношению к операции сложения, т.е. сумма двух и более кодовых слов тоже является кодовым словом.
Из этого свойства, видно, что векторы ошибок, совпадающие с кодовыми словами, не могут быть обнаружены декодером циклического кода.
Итак, векторы ошибок, которые нельзя обнаружить:
1 1 1 1 1 1 1
0 1 1 0 0 0 1
1 1 0 0 0 1 0
1 0 0 0 1 0 1
0 0 0 1 0 1 1
0 0 1 0 1 1 0
0 1 0 1 1 0 0
1 0 1 1 0 0 0
0 1 0 0 1 1 1
1 0 0 1 1 1 0
0 0 1 1 1 0 1
0 1 1 1 0 1 0
1 1 1 0 1 0 0
1 1 0 1 0 0 1
1 0 1 0 0 1 1
Найдем вероятность необнаруживаемой ошибки.
Имеем 7 векторов веса 4, 7 векторов веса 3 и 1 вектор веса 7.
5.2 Проверка правильности декодирования при отсутствии ошибок
5.3 Методика исследования способности кода исправлять ошибки
5.4 Методика проверки ошибочного декодирования в режиме исправления ошибок
5.5 Методика исследования способности кода обнаруживать ошибки
5.6 Методика проверки факта не обнаружения ошибки кодом
5.7. Таблица с разрешенными кодовыми комбинациями
Ответы на контрольные вопросы
Что такое расстояние Хемминга и кодовое расстояние ?
Расстояние Хемминга между двумя кодовыми словами равно числу единиц в сумме этих слов по модулю 2 , т.е. количеству разрядов, в которых различаются эти два кодовых слова. Например:
первое кодовое слово: 1000110,
второе кодовое слово: 0100010,
сумма по модулю два: 1100100 -> расстояние Хемминга равно 3.
Определение и основные свойства циклического кода?
Циклическим кодом называется такой линейный код, у которого при любом циклическом сдвиге какого-либо кодового слова получается другое кодовое слово.
Циклические коды относятся к классу линейных кодов и обладают всеми их свойствами. Дополнительным условием по отношению к циклическому линейному коду является условие замкнутости по отношению к операции циклического сдвига кодовых слов.
Поясните понятия: блочные, непрерывные, разделимые, неразделимые, итеративные, линейные, циклические коды ?
Линейные коды являются кодами блочными, регулярными. Для регулярных кодов задаются правила преобразования информационного слова длины k в кодовую последовательность длины n (n > k), а также правила декодирования. Наибольшее распространение получили линейные разделимые коды. Разделимым кодом называется код, в кодовых словах которого можно указать места информационных и проверочных символов.
Линейным кодом называют блочный (n, k) код, символы кодовых слов которого являются линейными комбинациями информационных символов.
Выводы
Было проведено исследование циклических кодов с помощью электронной блок-схемы, содержащей кодер и декодер. Из полученных результатов можно сделать вывод, что блок-схема работает верно, имеет свойства обнаружения и исправления ошибок в линейных кодах.