КОРРЕКТИРУЮЩИЕ КОДЫ

Цель занятия: Изучение практических приложений основных результатов теории помехоустойчивого кодирования дискретных сообщений в каналах связи с ошибками.

Литература: [1] – стр. 137 – 154

Контрольные вопросы

1. Классификация корректирующих кодов.
2. Принципы обнаружения и исправления ошибок.
3. Избыточность корректирующего кода, коэффициент обнаружения
   ошибок.
4. Связь обнаруживающей и исправляющей способности кода с кодовым расстоянием.
5. Определение числа проверочных элементов кода в зависимости от кодового расстояния.
6. Вероятность ошибки в кодовых комбинациях из n элементов, вероятность обнаружения ошибки или необнаружения ошибки кратности t.
7. Код с проверкой на четность, его свойства, вероятность необнаружения ошибки .
8. Код с постоянным весом, его свойства, вероятность необнаружения ошибки.
9. Инверсный код, его свойства, вероятность необнаружения ошибки.
10. Цепной код, его свойства, коэффициент избыточности.
11. Групповые систематические коды, производящая и проверочная матрицы.
12. Код Хэмминга и его построение по производящей матрице.
13. Улучшенный код Хэмминга, его свойства.
14. Циклические коды. Принципы построения циклических кодов и обнаружения ошибок.

Задачи

13.1. В 6-значной двоичной кодовой комбинации используется простейший код с проверкой на четность.

Задана амплитуда сигнала, способ модуляции, спектральная плотность помехи, скорость передачи сигналов.

Требуется определить:

• Вероятность искажения элементарной посылки p.
• Вероятность необнаруженной данным кодом ошибки
• Коэффициент обнаружения ошибки.

Исходные данные взять из таблицы вариантов к задаче 10.4.

13.2. В системе передачи данных используется циклический код.

Задано:

• число элементов кода n,
• число информационных элементов k,
• вероятность искажения элементарной посылки в канале с независимыми ошибками p.

Требуется определить:

• коэффициент обнаружения ошибок,
• коэффициент необнаружения ошибок,
• вероятность ошибки в комбинации из n элементов,
• вероятность необнаруженной данным кодом ошибки.

Исходные данные к задаче приведены в таблице вариантов.

Таблица вариантов к задаче 13.2

13.3. В системе передачи дискретной информации применён n-разрядный систематический двоичный код.

Определить:

• Сколько проверочных элементов должен иметь этот код для исправления однократных ошибок.
• Какой кратности ошибки может обнаруживать этот код.
• Чему равна избыточность этого кода.
• Чему равны коэффициент обнаружения и коэффициент исправления ошибок.

Число n для вариантов 1 – 10 определяется как номер варианта плюс число 5.
Число n для вариантов 11 – 20 равняется номеру варианта.
Число n для вариантов 21 – 30 определяется как номер варианта минус число 10.

13.4. Для передачи телеграфной информации применяется 7-значный код с постоянным весом 3:4.

Определить коэффициент обнаружения ошибок, избыточность кода и вероятность необнаруженной ошибки, если вероятность искажения элементарной посылки в канале с независимыми ошибками

p = 0,001N, где N – номер варианта.

13.5. В “улучшенном” коде Хемминга вводится дополнительный проверочный элемент для “сквозной” проверки кодовой комбинации на четность. Показать, можно ли подобным образом “улучшить” 7-значный код с постоянным весом путем введения восьмого проверочного элемента. Не произойдет ли при этом “ухудшение” кода?

13.6. Сравнить между собой 10-элементный инверсный код (k = 5, r = 5) и более простой 10-элементный код, в котором проверочные элементы повторяют информационные элементы (без инверсии). Перечислить все виды ошибок, которые не обнаруживает каждый из этих кодов. Привести расчетные формулы, определяющие вероятность необнаруженной ошибки каждым кодом в канале с независимыми ошибками и вычислить эти вероятности, если вероятность искажения элементарной посылки равна

p = 0,01 + 0,002N, где N – номер варианта.

13.7. В канале связи используется цепной код, в котором любой проверочный элемент определяется по рекуррентной формуле

bi = ai + ai+1 .

На вход декодера поступает последовательность посылок, заданная таблицей вариантов. Исправить обнаруженные ошибки в предположении, что в канале связи возникают достаточно редкие ошибки, а первым элементом заданной последовательности является информационная посылка. Пояснить, как Вы понимаете термин “достаточно редкие ошибки”. Что будет, если в канале связи появятся “пакеты” ошибок? Исходные данные приведены в таблице вариантов.

13.8. Найти проверочные элементы кода Хэмминга, состоящего из 5 информационных и 4 проверочных элементов и записать выражение для полученной 9-разрядной кодовой комбинации, если заданы информационные элементы кода,которые для разных вариантов определяются как номер варианта, записанный в виде 5-разрядного двоичного числа.

13.9. Используя результаты решения предыдущей задачи, построить
10-элементный “улучшенный” код Хэмминга, определить избыточность полученного кода и коэффициент исправления ошибок.

13.10. Код Хэмминга, содержащий 4 информационных и 3 проверочных элемента, используется для исправления одиночных ошибок. Определить, является ли заданная 7-значная комбинация разрешенной и если не является, исправить обнаруженную ошибку. Для разных вариантов заданная комбинация определяется как 5-разрядное двоичное число, равное номеру варианта, после которого приписаны элементы 11.

13.11. По заданной разрешенной 7-значной комбинации циклического кода (7, 4) построить производящую матрицу и с помощью производящей матрицы найти проверочные элементы для другой кодовой комбинации, если заданы информационные элементым кода. Записать полученную разрешенную комбинацию. Заданная разрешенная комбинация определяется как 100 + номер варианта (в десятичной системе счисления), переведенные в двоичную систему. Заданные информационные элементы кода новой комбинации определяются номером варианта, записанным в виде 5-разрядного числа.

13.12. Производящий многочлен циклического кода (8,5) имеет вид

g(x) = x3 + x + 1.

Найти проверочные элементы кода по заданным информационным элементам кода и записать полученную 7-значную комбинацию. Информационные элементы кода определяются номером варианта, заданного в виде 5-значного двоичного числа.

Таблица вариантов к задаче 13.7

13.13. Производящий многочлен циклического кода имеет вид

g(x) = x3 + x + 1.

Определить, является ли комбинация, поступившая на вход декодера, разрешённой. Для разных вариантов поступившая 7-значная комбинация определяется как номер заданного варианта, записанный в виде 5-разрядного двоичного числа, перед которым и после которого поставлено по одной единице.

назад | оглавление | вперёд