Никитин Г.И. Помехоустойчивые циклические коды

Подождите немного. Документ загружается.

1. Заданный порождающий полином необходимо преобразовать в двоичную

и в полиномиальную формы, а затем ввести с клавиатуры. Ввод полинома по сте-

пеням заключается в следующем: вводятся через запятую только степени поли-

нома, а затем нажимается клавиша <ENTER>. Например, полином Х

+ Х

Х+1 вводится как 10, 4, 3, 1, 0 <ENTER>. Программа допускает при двоичном вво-

де отбрасывание ведущих нулей. Так, слово 00101101 можно вводить как 101101.

Если введённые формы полинома не соответствуют исходной восьме-

ричной, то выводится сообщение об ошибке и повторяется ввод информации до

rex пор, пока она не будет введена правильно. Таким образом, довести до конца

работу можно только правильно выполнив каждый её пункт.

Зная длину кодового слова (n = 15) и порождающий полином, надо рас-

считать и ввести значения избыточности и скорости порождаемого этим полино-

мом циклического кода.

2. Этот раздел лабораторной работы посвящен процедурам умножения и де-

ления полиномов на исходный порождающий полином G(X) при помощи ЛПС (см.

подразделы 1.9 и 1.10).

На экране последовательно изображаются три "заготовки" ЛПС: две ЛПС

умножения и одна деления, с пронумерованными местами для перемычек. Задача

состоит в правильном размещении перемычек согласно порождающему полиному

G(X). Перемычки расставляются путём ввода через запятую их номеров.

3. В третьей части работы осуществляется синтез порождающей матрицы

циклического БЧХ-кода (15, 7) по его порождающему полиному с G(X) =Х

+Х

+1 (см. подразделы 1.5 и 1.6).

3.1. На экран выводятся основные данные БЧХ-кода (15,7): порождающий

полином и минимальное кодовое расстояние d = 5. Эти данные следует выписать,

так как они понадобятся в дальнейшем при работе.

3.2. Рассчитать и построчно ввести в двоичной форме порождающую кано-

ническую матрицу данного БЧХ-кода. Под канонической подразумевается матри-

ца, состоящая из двух подматриц - единичной и кодирующей. Такое построение

порождающей матрицы даёт разделимый БЧХ-код.

3.3. По порождающему полиному и минимальному кодовому расстоянию

требуется рассчитать и ввести проверочный полином данного БЧХ-кода, а также

количество гарантированно исправляемых и обнаруживаемых им ошибок.

3.4. Из канонической порождающей матрицы БЧХ-кода (15,7) получить поро-

ждающую матрицу укороченного БЧХ-кода (13, 5) и построчно ввести её.

4. Кодирование и декодирование циклическим БЧХ-кодом (15,7).

4.1. Полученное в начале работы информационное слово (десятичное

число в пределах от 1 до 127) ввести с клавиатуры.

4.2. Преобразовать информационное слово из десятичной формы в двоич-

ную, а затем в полиномиальную и последовательно ввести.

4.3. По информационному слову рассчитать кодовое слово разделимого

БЧХ-кода (15,7) и ввести его двоичный эквивалент. Кодовое слово можно вычис-

лить, умножив вектор информационного слова на порождающую матрицу или вы-

делив остаток от деления на порождающий полином информационного полинома,

предварительно умноженного на Х

, в случае применения кода (15,7).

4.4. ЭВМ троекратно рассчитывает случайный вектор ошибок, содержащий

одну, две и три ошибки, и выводит на экран исходное кодовое и искажённое сло-

во, отметив в нём ошибочные символы.

Необходимо вычислить и ввести двоичную форму синдрома, соответст-

вующего искажённому кодовому слову. ЭВМ проверяет правильность ввода и

формирует, исходя из полученного синдрома, шумовой вектор, который поразряд-

но суммируется по модулю 2 с искажённым кодовым словом. Таким образом вы-

числяется выводимое на экран исправленное кодовое слово. Затем ЭВМ рассчи-

тывает и отображает синдром исправленного кодового слова. Некоторые комби-

нации трёхкратных ошибок данный БЧХ-код не в состоянии исправить, так как его

минимальное кодовое расстояние равно 5.

Синдромы кодовых слов можно рассчитывать двумя способами: умножая

двоичное кодовое слово на транспонированную проверочную матрицу или деля

полином кодового слова на порождающий полином, определяя остаток (см. под-

раздел 1.4).

В конце лабораторной работы выводится информация о количестве до-

пущенных ошибок, а затем приглашение к вводу номера группы и фамилии сту-

дента, выполнившего работу. Эта информация автоматически дополняется датой

и временем выполнения работы, введённым полиномом и информационным сло-

вом, распределением ошибок исполнителя по разделам работы. Все эти данные

требуются для последующего просмотра преподавателем. Студентам, выполнив-

шим работу, необходимо сообщить об этом преподавателю для отметки в лабора-

торном журнале, предъявив данные о числе допущенных ошибок по разделам ра-

боты, подписанные оператором ЭВМ.

3. КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Пояснить принципы помехоустойчивого кодирования.

2. Циклические коды и их особенности.

3. Порождающий и проверочный полиномы ЦК и их основные особенности.

4. Укороченные ЦК. Порождающие и проверочные матрицы укороченных ко-

дов и их порождающие полиномы.

5. Принципы кодирования и декодирования ЦК при помощи ЛПС.

6. Построение канонической и порождающей матрицы по порождающему или

проверочному полиномам. Покажите на примере.

7. Определите верхнюю границу минимального кодового расстояния задан-

ного (n, k) ЦК.

8. Закодируйте БЧХ - кодом (15,7) произвольное кодовое слово при помощи

порождающей матрицы и полинома.

9. Охарактеризуйте различие между разделимыми и неразделимыми кодами.

Приведите примеры.

10. Объясните суть синдромного метода декодирования и его отличие от де-

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

11. Почему синдром исправленного кодового слова всегда равен нулю, даже

если кратность ошибки превосходит корректирующую способность кода и поэтому

исправленное кодовое слово неверно?

12. Как связаны между собой минимальное кодовое расстояние и кратности

исправляемых и обнаруживаемых им ошибок?

13. В чём заключается трудность декодирования с исправлением ошибок?

14. При обнаружении ошибки в кодовой комбинации на стороне приёма како-

вы пути её исправления?

15. В чём состоят особенности кодов Абрамсона и Файра, в каких случаях их

целесообразно применять?

16. Какое главное отличие кодов Рида-Соломона от БЧХ-кодов, в каких

случаях находят применение коды Рида-Соломона?

17. Охарактеризуйте достоинства и особенности кода Голея.

18. Дайте определение оператора сдвига, с какой целью он применяется

при циклическом кодировании?

Литература

1. Никитин Г. И. Первичные коды: Метод. указ./ ЛИАП. Л., 1984. 28 с.

2. Никитин Г. И. Эффективные коды: Метод, указ./ ЛИАП. Л., 1987. 28 с.

3. Никитин Г. И., Антипова И. Б., Красновидов А. В. Корректирующие

коды: Метод. указ./ ЛИАП. Л., 1989. 32 с.

4. Журавлев А. К., Никитин Г. И. Радиотехнические системы передачи

информации: Учеб. пособие/ ЛИАП. Л., 1984. 86 с.

5. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер.

с англ. М.: Мир, 1986. 576 с.

6. Питерсон У., Уэлдон Э, Коды, исправляющие ошибки: Пер. с англ. М.:

Мир, 1976. 600 с.

7. Аршинов М. Н., Садовский Л. Е. Коды и математика (рассказы о кодирова-

нии). М.: Наука, 1983. 144 с.

8. Харкевич А. А. Борьба с помехами. М.: Физматиздат, 1963. 276 с.

9. Колесников В. Д., Мирончиков Е. Т. Декодирование циклических кодов. М.:

Связь, 1968.

10. Замрий А. С. Помехоустойчивые коды: Учеб. пособие/ ЛВВИУС. Л.,

1990. 58 с.

11. Варакин Л. Е, Системы связи с шумоподобными сигналами. М.: Радио и

связь, 1985. 384 с.

12. Никитин Г.И., Поддубный С.С. Помехоустойчивые циклические коды:

Учеб.пособие/ СПбГУАП. СПб., 1998. 72 с.

СОДЕРЖАНИЕ

Список основных сокращений.................................... ……………………………. 3

Введение ................................................................... ……………………………. 4

1. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ПОДГОТОВКЕ

К ЛАБОРАТОРНОЙ РАБОТЕ ….. ……………………………………………… 4

1.1. Классификация корректирующих кодов............... …………………………… 4

1.2. Полиномиальное определение циклических кодов

и операции с ними ........ ......................................... ……………………………. 5

1.3 Порождающие полиномы циклических кодов..... ……………………………. 7

1.4. Принципы формирования и обработки разрешённых кодовых

комбинаций циклических кодов ............................ ……………………………. 10

1.5. Построение порождающих и проверочных матриц циклических кодов …. 15

1.6. Укороченные циклические коды.......................... ……………………………. 18

1.7. Циклические коды Боуза—Чоудхури—Хоквингема ………………………. 20

1.8. Структурный состав линейных переключательных схем …………………. 21

1.9. Умножение полиномов на базе ЛПС................... ……………………………. 22

1.10. Деление полиномов на базе Л ПС ………………………………………….. 24

1.11. Кодирующее и декодирующее устройства для кода Хемминга (7,4)…… 26

1.12. Принципы построения декодирующих устройств

для циклических кодов с исправлением ошибок ……………………………… 28

2. ПОРЯДОК ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ

"ЦИКЛИЧЕСКИЕ КОДЫ" …………………………………………………………… 30

3. КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ ………………………………………. 32

Литература ……………………………………………………………………… 33

Графика и компьютерная вёрстка

Романова М.Я. 2003 г.