Передача информации по каналу с решающей обратной связью

Аннотация

Тема: Передача информации по каналу с решающей обратной связью.

Данная выпускная работа посвящена использованию помехоустойчивых кодов, в частности, циклического кода, у которого кодовое расстояние равно 4.

В работе излагаются этапы и результаты разработки программы, реализующей кодирование циклическим кодом (14,9), приводятся анализ поставленной задачи, ход разработки, результаты решения. Также разработаны структурная, функциональная и принципиальная схемы, реализующие кодирование, декодирование, исправление и обнаружение ошибок циклическим кодом (14,9).

• Аннотация 1

• Введение

  3

• 1. Постановка задачи 5
• 1.1 Анализ технического задания 5
• 1.2 Теоретическое введение 6
• 1.2.1 Способы передачи информации по каналам связи 6
• 1.2.2 Основные понятия о помехозащищенном кодировании 12
• 1.2.3 Помехозащищенные коды. Циклический код 18
• 1.2.4 Методы построения циклических кодов 19
• 1.2.5 Методы декодирования циклических кодов и обнаружения ошибок 33
• 1.3 Математическая модель 35
• 1.4 Построение образующей матрицы 36
• 1.5 Расчет достоверности передаваемых сообщений 38
• 1.6 Выводы 40
• 2. Техническая реализация кодера, декодера и решателей 41
• 2.1 Модульная структура кодера и его работа 41
• 2.2 Модульная структура декодера и его работа 43
• 2.3 Модульная структура решателя кодера и его работа 46
• 2.4 Модульная структура решателя декодера и его работа 48
• 2.5 Выбор микросхем для реализации кодера, декодера и решателей 49
• 2.6 Описание функциональной схемы кодера и решателя кодера 56
• 2.7 Описание функциональной схемы декодера и решателя декодера 57
• 2.8 Описание принципиальной схемы кодера и решателя кодера 58
• 2.9 Описание принципиальной схемы декодера и решателя декодера 61
• 2.10 Выводы 62
• 3. Описание программных средств, разработанных в ходе реализации проекта 64
• 3.1 Структура системы 64
• 3.2 Входные данные, форма представления результатов 64
• 3.3 Спецификация на программу в целом. 64
• 3.4 Системные требования 66
• 3.5 Спецификация на программу в целом. 66
• 4. Результативная часть 67
• 4.1 Тестирование 67
• 4.2 Описание пользовательского интерфейса 68
• 4.3 Инструкция пользователю. 68
• 4.4 Выводы 68
• 5.

  Заключение

  69

• Текст программы на языке VHDL для решателя декодера 70
• Документированный текст программы 71

Деятельность людей связана с переработкой и использованием материалов, энергии и информации. Соответственно развивались научные технические дисциплины, отражающие вопросы технологии, энергетики и информатики. Информационная техника является сравнительно новой отраслью, получающей наибольшее развитие на этапе разработки и применения электронных вычислительных машин (ЭВМ) и автоматизированных систем управления (АСУ).

Информационная наука теперь находит применение в самых разнообразных областях теории и практики. Центральной ветвью является теория связи, созданная Шенноном на основе теории вероятностей.

С передачей и обработкой информации связаны действия любого автоматического устройства, поведение живого существа, творческая деятельность человека, развитие науки и техники, экономические и социальные преобразования в обществе и сама жизнь. Для более эффективного использования информации необходимо обмениваться информацией, что невозможно без её передачи по каналам связи.

При передаче информации по каналам связи может происходить искажение передаваемой информации. Для предотвращения потерь полезной информации существуют различные методы защиты. Одним из них является кодирование информации при помощи помехозащищённых кодов.

Двоичный код на все комбинации не является помехозащищённым, так как его комбинации отличаются друг от друга лишь в одном разряде, что не позволяет на приёмной стороне обнаружить и исправить возникшие ошибки. В этой связи возникает необходимость построения помехозащищённого кода.

Помехозащищённые коды — это коды, которые позволяют обнаруживать и исправлять ошибки, то есть корректировать полученные сообщения. Для достижения помехозащищенности можно ввести избыточность добавлением дополнительных контрольных разрядов.

Существует много различных алгоритмов построения помехозащищённых кодов. В данной работе рассматривается код (14,9). Он относится к группе циклических кодов. А именно, он относится к циклическим кодам, обнаруживающим 1 и исправляющим 1 ошибку.

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

1. Постановка задачи

1.1 Анализ технического задания

В соответствии с техническим заданием требуется построить математическую модель циклического кода с кодовым расстоянием 4, для количества букв алфавита сообщений 256. Требуется рассчитать длину кода и его корректирующую способность, найти образующую матрицу кода.

Разработать программу, реализующую кодирование и декодирование разработанным кодом.

Реализовать схему для его кодирования и декодирования на уровне функциональной и принципиальной схемы.

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

Расчетно-пояснительная записка содержит:

Введение

;

Содержание;.

Постановочную часть;

2. Разработку схемы кодирующего, декодирующего и решающих устройств;

3.Описание разработанной программы;

4.Результативную часть;

5.Выводы и заключение;

6.

Список литературы

;

7.Приложения;

В записке содержатся следующие приложения:

Структурную схему передачи данных с РОС;

Функциональная схема кодера и решателя кодера;

Функциональная схема декодера и решателя декодера;

Принципиальная схема кодера и решателя кодера Перечень элементов;

Принципиальная декодера и решателя декодера;

Перечень элементов;

Документированный текст программы решателя декодера;

Временные диаграммы;

Документированный текст программы;

Экранные формы;

Техническое задание

1.2 Теоретическое введение

1.2.1 Способы передачи информации по каналам связи

Передача информации с повторением (накоплением). Такой метод передачи применяют для повышения достоверности при отсутствии обратного канала, хотя нет принципиальных ограничений для его использования и при наличии обратной связи. Иногда такой метод классифицируют как прием сообщений с накоплением. Сущность метода заключается в передаче одного и того же сообщения несколько раз, запоминании принятых сообщений, сравнении их поэлементно и составлении сообщения, включая элементы, выбранные «по большинству». Предположим, что трижды передана одна и та же кодовая комбинация 1 010 101. Во всех трех передачах она подверглась воздействию помех и была искажена:

Приемник поразрядно сравнивает три принятых символа и проставляет те символы (под чертой), количество которых в данном разряде преобладает.

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

Таким образом, высокая помехоустойчивость метода передачи информации с повторением (накоплением) основана на том, что сигнал и помехи в канале не зависят друг от друга и изменяются по разным законам (сигнал периодичен, а помеха случайна), поэтому повторяющаяся комбинация в каждой передаче, как правило, будет искажаться по-разному. Вследствие этого на приеме накопление, то есть суммирование сигнала, возрастает пропорционально числу повторений, тогда как сумма помехи возрастает по другому закону. Если считать, что помехи и сигнал независимы, то суммируются средн-ие квадраты и средний квадрат суммы возрастает пропорционально первойстепени. Поэтому при n повторениях отношение сигнал/помеха увеличивается в n раз, причем это происходит без увеличения мощности сигнала. Однако это достигается за счет усложнения аппаратуры и возрастания времени передачи или полосы частот в случае, если сигнал передается на нескольких частотах одновременно во времени. Кроме того, при зависимых ошибках и пачках ошибок помехоустойчивость системы снижается.

Передача информации с обратной связью. Помехоустойчивость передачи без обратной связи (ПБОС) обеспечивается следующими способами: помехоустойчивым кодированием, передачей с повторением, одновременной передачей по нескольким параллельным каналам. В ПБОС применяются обычно коды с исправлением ошибок, что связано с высокой избыточностью и усложнением аппаратуры. Передача с обратной связью (ПОС) во многом устраняет указанные недостатки, так как позволяет применять менее помехоустойчивые коды, обладающие, как правило, меньшей избыточностью. В частности, можно использовать коды с обнаружением ошибок. Преимуществом обратного канала является также возможность контроля работоспособности объекта, принимающего информацию.

При ПОС вводят понятие прямого канала, т. е. канала от передатчика к приемнику, например передается сигнал команды с пункта управления (ПУ) на контролируемый пункт (КП). Обратным каналом при этом явится передача сообщения с КП на ПУ о принятии сигнала команды, причем по обратному каналу могут передаваться как сообщение только о том, что сигнал принят на входе КП (в этом случае контролируется лишь прохождение сигнала по каналу связи), так и сведения о полном выполнении команды. Возможна и обратная связь, дающая сведения о поэтапном прохождении сигнала команды по тракту приема.

Рассмотрим отдельные виды передачи с обратной связью.

Передача с информационной обратной связью (ИОС). Если сообщение передается в виде непомехозащищенного кода, то в кодирующем устройстве данный код может быть преобразован в помехозащищенный. Однако, поскольку в этом обычно нет необходимости, кодирующее устройство представляет собой регистр для превращения простого параллельного кода в последовательный. Одновременно c передачей по прямому каналу сообщение запоминается в накопителе на передатчике (рис. 1.1а). На контролируемом пункте принятое сообщение декодируется и также запоминается в накопителе. Однако получателю сообщение передается не сразу: сначала оно поступает через обратный канал на пункт управления. В схеме сравнения ПУ происходит сравнение принятого сообщения с переданным. Если сообщения совпадают, то формируется сигнал «Подтверждение» и происходит передача последующих сообщений (иногда перед посылкой последующего сообщения на КП сначала посылается сигнал «Подтверждение» о том, что предыдущее сообщение было принято верно и с накопителя можно передать информацию получателю). При несовпадении сообщений, что свидетельствует об ошибке, формируется сигнал «Стирание». Этот сигнал запирает ключ для прекращения передачи очередного сообщения и посылается на КП для уничтожения записанного в накопителе сообщения. После этого с ПУ производится повторная передача сообщения, записанного в накопителе.

Рис. 1.1а. Способ передачи информации с ИОС.

В системах с ИОС ведущая роль принадлежит передающей части, так как она определяет наличие ошибки, приемник только информирует передатчик о том, какое сообщение им получено. Имеются различные варианты передачи с ИОС. Так, существуют системы с ИОС, в которых передача сигналов происходит непрерывно и прекращается лишь при обнаружении ошибки: передатчик посылает сигнал «Стирание» и повторяет передачу. Системы с ИОС, в которых по обратному каналу передается вся информация, переданная на КП, называются системами с ретрансляционной обратной связью. В некоторых системах с ИОС передается не вся информация, а только некоторые характерные сведения о ней (квитанции). Например, по прямому каналу передаются информационные, а по обратному каналу — контрольные символы, которые будут сравниваться на передатчике с предварительно записанными контрольными символами. Имеется вариант, в котором после проверки принятого по обратному каналу сообщения и обнаружения ошибки передатчик может либо повторить его (дублирование сообщения), либо послать дополнительную информацию, необходимую для исправления (корректирующая информация). Число повторений может быть ограниченным или неограниченным.

Обратный канал используют для того, чтобы определить, необходима ли повторная передача информации. В системах с ИОС повышение достоверности передачи достигается путем повторения информации только при наличии ошибки, тогда как в системах без обратной связи (при передаче с накоплением) повторение осуществляется независимо от искажения сообщения. Поэтому в системах с ИОС избыточность информации значительно меньше, чем в системах с ПБОС: она минимальна при отсутствии искажений и увеличивается при ошибках. В системах с ИОС качество обратного канала должно быть не хуже качества прямого во избежание искажений, которые могут увеличить число повторений.

Передача с решающей обратной связью (РОС). Переданное с передатчика по прямому каналу сообщение принимается на приемнике (рис. 1.1б), где оно запоминается и проверяется в декодирующем устройстве (декодере). Если ошибок нет, то из накопителя сообщение поступает к получателю информации, а через обратный канал на передатчик подается сигнал о продолжении дальнейшей передачи (сигнал продолжения). Если ошибка обнаружена, то декодер выдает сигнал, стирающий информацию в накопителе. Получателю сообщение не поступает, а через обратный канал на передатчик подается сигнал о переспросе или повторении передачи (сигнал повторения или переспроса). На передатчике сигнал повторения (иногда называемый решающим сигналом) выделяется приемником решающих сигналов, а переключающее устройство отключает вход кодера от источника информации и подключает его к накопителю, что позволяет повторить переданное сообщение. Повторение сообщения может происходить несколько раз до его правильного приема.

Рис. 1.1б. Способ передачи информации с РОС.

При передаче с РОС ошибка определяется приемником. Для этого передаваемое сообщение должно кодироваться обязательно помехозащищенным кодом, что позволяет приемнику выделить разрешенную комбинацию (сообщение) из неразрешенных. Это означает, что передача с РОС осуществляется с избыточностью. Достоверность передачи в системах РОС определяется выбором кода и защитой решающих сигналов повторения и продолжения. Последнее не представляет особых трудностей, так как эти сигналы несут одну двоичную единицу информации и могут передаваться достаточно помехоустойчивым кодом.

Системы с РОС, или системы с переспросом, подразделяют на системы с ожиданием решающего сигнала и системы с непрерывной передачей информации.

В системах с ожиданием передача новой кодовой комбинации или повторение переданной происходит только после поступления на передатчик сигнала запроса.

В системах с непрерывной передачей происходит непрерывная передача информации без ожидания сигнала запроса. Скорость передачи при этом выше, чем в системах с ожиданием. Однако после обнаружения ошибки по обратному каналу посылается сигнал переспроса и за время прихода на передатчик с последнего уже будет передано какое-то новое сообщение. Поэтому системы с непрерывной передачей необходимо усложнять соответствующей блокировкой приемника, чтобы он не принимал информацию после обнаружения ошибки.

Для сравнения эффективности системы без обратной связи, в которой применяется код Хэмминга с исправлением одной ошибки, и системы с РОС, использующей простой код, вводят понятие коэффициента эффективности. Этот коэффициент учитывает уменьшение вероятности ошибочного приема и затраты на его достижение, выигрыш в защите от ошибок (в случае применения указанных кодов), относительное снижение скорости передачи и схемную избыточность, связанные с использованием разных кодов. Итоговое сравнение показало, что в отличие от системы без обратной связи, использующей сложный код, система с РОС дает выигрыш в 5,1 раза. Высокая эффективность систем с РОС обеспечила их широкое распространение.

Сравнительный анализ достоверности передачи систем с ИОС и РОС, показал, что:

1) системы с ИОС и РОС обеспечивают одинаковую достоверность передачи при одинаковых суммарных затратах энергии сигналов в прямом и обратном каналах при условии, что эти каналы симметричны и имеют одинаковый уровень помех;

2) системы с ИОС обеспечивают более высокую достоверность передачи, чем Системы с РОС при относительно слабых помехах в обратном канале в отличие от прямого. При отсутствии помех в обратном канале системы с ИОС обеспечивают безошибочную передачу сообщений по основному каналу;

3) при сильных помехах в обратном канале более высокую достоверность обеспечивают системы с РОС;

4) при пачках ошибок в прямом и обратном каналах более высокую достоверность обеспечивают системы с ИОС.

1.2.2 Основные понятия о помехозащищенном кодировании

Помехозащищенными (или корректирующими) называются коды, позволяющие обнаружить и исправить ошибки в кодовых комбинациях. Отсюда и деление этих кодов на две большие группы: 1) коды с обнаружением ошибок; 2) коды с обнаружением и исправлением ошибок.

Принципы обнаружения и исправления ошибок кодами хорошо иллюстрируются с помощью геометрических моделей. Любой n-элементный двоичный код можно представить n-мерным кубом (рис. 1.2), в котором каждая вершина отображает кодовую комбинацию, а длина ребра куба соответствует одной единице. В таком кубе расстояние между вершинами (кодовыми комбинациями) измеряется минимальным количеством ребер, находящихся между ними, обозначается d и называется кодовым расстоянием Хэмминга.

Таким образом, кодовое расстояние — это минимальное число элементов, в которых любая кодовая комбинация отличается от другой (по всем парам кодовых слов). Например, код состоит из комбинаций 1011, 1101, 1000 и 1100. Сравнивая первые две комбинации, путем сложения их по модулю 2 находим, что d=2. Сравнение первой и третьей комбинаций показывает, что и в этом случае d=2. Наибольшее значение d=3 обнаруживается при сравнении первой и четвертой комбинаций, а наименьшее d=1 — второй и четвертой, третьей и четвертой комбинаций. Таким образом, для данного кода минимум расстояния d_min=l.

При n=1 n-мерный куб превращается в прямую длиной d=1, на одном конце которой располагается 1, а на другом — 0. При n = 2 четыре возможные комбинации (N=2²=4) располагаются на четырех вершинах квадрата. При этом комбинации 00 и 11, а также 10 и 01 отличаются друг от друга в двух разрядах, т. е. d=2.

Кодовое расстояние между двумя комбинациями двоичного кода равно числу единиц, полученных при сложении этих комбинаций по модулю 2, например 1001=11 и 0011=11. Такое определение кодового расстояния удобно при большой разрядности кодов. Так, складывая комбинации

110 101 111,

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

При n = 3 восемь кодовых комбинаций размещаются в вершинах трехмерного куба.

Рис. 1.2. Геометрическая модель двоичных кодов Трехмерный куб строится так (рис. 1.2), что одна из его вершин лежит в начале координат. Каждой вершине куба приписывается кодовая комбинация по следующему правилу: на i-м месте кодовой комбинации ставится 0, если проекция этой вершины на i-ю ось координат равна нулю, и 1, если проекция равна единице. Например, требуется узнать, какую следует записать комбинацию в вершине A₆ (рис. 1.2). Проецируя эту вершину на ось Х₁, получим единицу. На втором месте комбинации запишется также 1 (проекция на ось X₂ равна единице). Так как проекция на ось Х₃ равна нулю (проекция в начало координат), то на третьем месте комбинации запишется 0. Следовательно, вся комбинация в вершине A₆ запишется как 110.

Если использовать все восемь слов, записанных в вершинах куба, то образуется двоичный код на все сочетания. Как было показано, такой код является непомехоустойчивым. Если же уменьшить число используемых комбинаций с восьми до четырех, то появится возможность обнаружения одиночных ошибок. Для этого выберем только такие комбинации, которые отстоят друг от друга на расстояние d = 2, например 000, 110, 011 и 101. Остальные кодовые комбинации не используются. Если будет принята комбинация 100, то очевидно, что при ее приеме произошла одиночная ошибка.

Представленные комбинации построены по определенному правилу, а именно содержат четное число единиц, а принятая комбинация 100 — нечетное. Можно утверждать, что комбинация 100 образовалась при искажении разряда одной из разрешенных комбинаций, но определить, какая именно комбинация искажена, невозможно. Поэтому такие или подобные им коды называют кодами с обнаружением ошибок.

Кроме указанной группы комбинаций в том же трехмерном кубе может быть получена еще одна группа комбинаций с кодовым расстоянием d=2 (111, 001, 010 и 100). В этих кодовых комбинациях нечетное число единиц и каждая из комбинаций могут быть использованы для обнаружения ошибки, возникшей при передаче, так как при одиночном искажении в комбинации будет четное число единиц. Однако, если необходимо получить код с обнаружением одиночной ошибки, в передаче может участвовать только одна группа, т. е. четыре комбинации из возможных восьми. В противном случае получится непомехоустойчивый код, в котором будут встречаться комбинации с d=l.

Таким образом, в помехозащищенных кодах есть комбинации разрешенные, составленные по определенному правилу, и запрещенные, не соответствующие этому правилу.

Так, если из восьми комбинаций трехразрядного кода образованы четыре комбинации, позволяющие обнаружить одиночную ошибку (например, 111, 001, 010 и 100), то эти комбинации являются разрешенными, а остальные четыре (000, 011, 101 и 110) — запрещенными, которые должны фиксироваться на приеме как искаженные. Иногда совокупность разрешенных кодовых комбинаций, которые при заданных возможных искажениях не могут перейти друг в друга, называют системой непереходящих сигналов.

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

Таким образом, установлено, что уменьшение числа используемых комбинаций приводит к повышению помехоустойчивости кода. Если идти дальше по этому пути и еще больше ограничить число разрешенных комбинаций, то можно создать код не только с обнаружением, но и с исправлением ошибки.

Выберем в трехмерном кубе такие вершины, кодовые обозначения которых отличались бы друг от друга на d=3. Такие вершины расположены на концах пространственных диагоналей куба. Их может быть только четыре пары: 000 и 111, 001 и 110, 100 и 011, 010 и 101. Однако из этих четырех пар для передачи можно брать только одну любую пару, так как большее число пар приведет к тому, что в передаче будут использоваться комбинации, отличающиеся друг от друга на d<3.

Код, образованный по такому правилу, может исправить одиночную ошибку или обнаружить две ошибки без их исправления. Пусть, например, передается код, состоящий из комбинаций 001 и 110. На приеме получена комбинация 100. Сравнение ее с исходными комбинациями показывает, что от комбинации 110 она отличается в одном (втором) разряде, а от комбинации 001 — в двух разрядах. Если считать, что сделана одна ошибка, то полученную комбинацию 100 следует исправить на 110.

От разрешённой комбинации 001 отличаются нa d=l комбинации 011, 000 и 101, а от комбинации 110 — комбинации 111, 100 и 010. Они и являются своеобразными комбинациями-спутниками, которые после приема можно относить к той или иной исходной комбинации.

Когда говорят об исправлении одиночной ошибки, считают, что вероятность двойной ошибки в канале связи пренебрежимо мала. Если такая вероятность достаточно велика, то код с d = 3 можно использовать для обнаружения двойных ошибок, но при этом исправить одиночную ошибку он уже не может. Действительно, если в нашем примере была принята комбинация 100, то нельзя утверждать, что была передана комбинация 110, так как при двойных ошибках это могла быть и искаженная комбинация 001.

Таким образом, дальнейшее повышение помехоустойчивости кода связано с увеличением кодового расстояния d, что приводит к увеличению избыточности (вместо восьми комбинаций используются только две).

Корректирующая способность кода зависит от кодового расстояния: а) при d=1 ошибка не обнаруживается; б) при d = 2 обнаруживаются одиночные ошибки; в) при d = 3 исправляются одиночные ошибки или обнаруживаются двойные ошибки. В общем случае

d = r + s + 1,

где d — минимальное кодовое расстояние; r — число обнаруживаемых ошибок; s — число исправляемых ошибок.

При этом обязательным условием является r? s. Так, в нашем примере d = 3, и если r = s = l, то код может обнаружить одну ошибку и исправить ее. Если r =2, s=0, то код может только обнаружить две ошибки. Как следует из уравнения, для исправления одной ошибки и обнаружения двух ошибок необходимо, чтобы d = 2 + 1 + 1 =4. При d=4 может быть также вариант, когда r=3, s=0. Если d=5, то могут быть три варианта: r = s = 2; r=3, s=l; r = 4, s=0.

Если код только обнаруживает ошибки, то

d=r + l, т. е. r = d — 1.

Если код только исправляет ошибки, то

d=2s+1, т. е. s=(d — 1)/2

Итак, геометрические модели позволяют просто строить малоразрядные корректирующие коды. Однако при длине кода n>3 геометрической моделью пользоваться трудно, так как она должна быть многомерной. Поэтому для построения многоразрядных помехоустойчивых кодов используют различные правила и методики, к рассмотрению которых и перейдем.

1.2.3 Помехозащищенные коды. Циклический код

Циклические коды относятся к числу блоковых систематических кодов, в которых каждая комбинация кодируется самостоятельно (в виде блока) таким образом, что информационные k и контрольные m символы всегда находятся на определенных местах.

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

Теория циклических кодов базируется на теории групп и алгебре многочленов над полем Галуа.

Многочлен (полином), который можно представить в виде произведения многочленов низших степеней, называют приводимым (в данном поле), в противном случае — неприводимым. Неприводимые многочлены играют роль, сходную с простыми числами в теории чисел. Неприводимые многочлены Р (Х) можно записать в виде десятичных или двоичных чисел либо в виде алгебраического многочлена (табл. 1.1).

Таблица 1.1 Неприводимые многочлены и их эквиваленты

В табл. 1.1 указаны все неприводимые многочлены до пятой степени; включительно, используемые для построения циклических кодов. Многочлены более высоких степеней приводятся лишь выборочно.

Многочлен в поле двоичных чисел называется неприводимым, если он делится без остатка только на себя или на единицу; что касается многочленов, приведенных в табл. 1.1, то это определение справедливо только для конечного поля двоичных чисел.

В основу циклического кодирования положено использование неприводимого многочлена Р (Х), который применительно к циклическим кодам называется образующим, генераторным или производящим многочленом (полиномом).

1.2.4 Методы построения циклических кодов

В качестве информационных символов k для построения циклических кодов берут комбинации двоичного кода на все сочетания. В общем случае, если заданную кодовую комбинацию Q (X) умножить на образующий многочлен Р (Х), получится циклический код, обладающий теми или иными корректирующими свойствами в зависимости от выбора Р (Х). Однако в этом коде контрольные символы m будут располагаться в самых разнообразных местах кодовой комбинации. Такой код не является систематическим, что затрудняет его схемную реализацию. Ситуацию можно значительно упростить, если контрольные символы приписать в конце кода, то есть после информационных символов. Для этой цели целесообразно воспользоваться следующим методом.

1. Умножаем кодовую комбинацию G (X), которую мы хотим закодировать, на одночлен, имеющий ту же степень, что и образующий многочлен Р (Х).

2. Делим произведение на образующий многочлен Р ():

(1.1)

где Q (X) — частное от деления; R (X) — остаток.

Умножая выражение (1.1) на Р (Х) и перенося R (X) в другую часть равенства, согласно правилам алгебры двоичного поля, т. е. без перемены знака на обратный, получаем

(1.2)

Таким образом, согласно равенству (1.2), циклический код, т. е. закодированное сообщение F (X), можно образовать двумя способами:

1) умножением одной из комбинаций двоичного кода на все сочетания [комбинация Q (X) принадлежит к той же группе того же кода, что и заданная комбинация G (X)] на образующий многочлен Р (Х);

2) умножением заданной кодовой комбинации G (X) на одночлен, имеющий ту же степень, что и образующий многочлен Р (Х), с добавлением к этому произведению остатка R (X), полученного после деления произведения на образующий многочлен Р (Х).

Пример 1.1. Требуется закодировать одну из комбинаций двоичного кода 1101, что соответствует .

Не останавливаясь на выборе образующего многочлена Р (Х), о чем будет сказано далее, возьмем из табл. 1.1 многочлен Р (Х³)=Х³+Х+1>11>1011.

Умножая G (X) на, который имеет третью степень, получим

.

От умножения степень каждого многочлена повысилась, что эквивалентно приписыванию трех нулей к многочлену, выраженному в двоичной форме.

Разделив произведение на образующий многочлен, согласно (1.1) получим

или в двоичном эквиваленте

Таким образом, в результате деления получаем частное Q (X) той же степени, что и G (X):

и остаток:

.

В итоге комбинация двоичного кода, закодированная циклическим кодом, согласно (1.2) примет вид

F (X)= 1111*1011 = 1 101 000 + 001 = 1 101 001.

Действительно, умножение 1111*1011 (первый способ) дает тот же результат, что и сложение 1 101 000 + 001 (второй способ).

Циклические коды, обнаруживающие одиночную ошибку (d=2). Код, образованный многочленом Р (Х)=Х+1, обнаруживает не только одиночную ошибку, но и любое нечетное число ошибок.

Предположим, что необходимо закодировать сообщение G (Х)=Х³+ +Х²+X+1>1101 с помощью образующего многочлена P (Х)=Х+1>11.

Умножим G (X) на Х^m, что эквивалентно добавлению нуля справа, так как m=1, поскольку Р (Х) имеет первую степень: (Х³+Х²+1)X= Х⁴+Х³+X>11 010.

Разделив полученное выражение на Р (Х), найдем, что остаток R (X)=1. Следовательно, кодовый многочлен циклического кода в соответствии с уравнением (1.2) будет иметь вид

F (X)= G (X)Х^m + R (X)= Х⁴ + Х³ +X + 1> 11 010 + 1 = 11 011.

Таким образом, в этом закодированном сообщении 11 011 n = 5, k=4 и m=1, то есть информационным символом является комбинация 1101, а контрольным — единица в младшем разряде.

Сообщение, которое было закодировано (1101), является одной из 16 комбинаций четырехразрядного кода. Если требуется передать все эти сообщения в закодированном виде, то каждое из них следует кодировать так же, как и комбинацию 1101. Однако проделывать дополнительные 15 расчетов (в общем случае 2^k расчетов) нет необходимости. Это можно сделать проще, путем составления образующей (порождающей) матрицы.

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

Число столбцов транспонированной единичной матрицы равно числу информационных символов k. Матрица дополнений получается из остатков от деления единицы с нулями на образующий многочлен Р (Х), выраженный в двоичном эквиваленте. Число остатков равно числу информационных символов.

Как следует из результатов деления единицы с нулями на Р (Х)=Х+1>11, все остатки оказываются равными единице. Поэтому образующая матрица имеет вид

Единичная Матрица

транспо дополнений

нирован

ная матрица

Четыре кодовые комбинации, из которых состоит образующая матрица, являются первыми кодовыми комбинациями циклического кода. Пятая комбинация нулевая, а так как в четырехразрядном непомехозащищенном коде всего N=2⁴ =16 комбинаций, то остальные 11 ненулевых комбинаций находят суммированием по модулю 2 всевозможных комбинаций строк образующей матрицы:

5. 9. 13.

6. 10. 14.

7. 11. 15.

8. 12. 16.

Сгруппируем полученные комбинации следующим образом:

Видно, что в первом столбце от комбинации к комбинации две рядом стоящие единицы сдвигаются на один символ влево, во втором столбце циклически сдвигаются две единицы, не стоящие рядом друг с другом, а в третьем столбце происходит циклический сдвиг четырех единиц. Этот циклический сдвиг одной комбинации по отношению к другой и определил название кодов — циклические.

Заметим, что циклический сдвиг является результатом умножения кодовой комбинации на X. Действительно, вторую комбинацию можно записать как 101> Х² + 1, седьмую — как (Х² + 1) Х = X³ + X>1 010 и т. п. Если при умножении на X степень становится равной X^m+l, то полученный результат нужно разделить на Х+1. Например, если комбинацию 10 101> Х⁴+ +Х² + 1 умножить на X, то получим Х⁵ + Х³ + X. Деля полученное выражение на Х⁵ + 1, найдем остаток Х³ + Х + 1 > 1 011. Многочлен 1 011 и является результатом циклического сдвига на один разряд влево многочлена 10 101.

Рассмотрение полученных комбинаций показывает, что все они имеют четное число единиц. Действительно, контрольные символы оказываются равными единице при нечетном числе единиц в исходной комбинации и нулю при четном числе единиц. Таким образом, циклический код с обнаружением одиночной ошибки является обычным кодом с четным числом единиц.

Циклические коды с d = З. Эти коды могут обнаруживать одиночные и двойные ошибки или обнаруживать и исправлять одиночные ошибки.

1. Выбор числа контрольных символов. Есть два способа выбора числа m. При первом способе исходят из того, что число контрольных символов m= = n — k зависит от числа информационных символов, а значит, и от длины всей кодовой комбинации. Выбор m производится, как и для кода Хэмминга, с исправлением одиночной ошибки. Условие может быть записано в виде

(1.3)

где Е" — знак округления в сторону большего значения.

При втором способе число контрольных символов определяется по эмпирической формуле

m=Е" Iog₂[(k +1) + E" Iog₂ (k + 1)]. (1.4)

В основу выбора m в последнем выражении положено значение числа информационных разрядов. Это удобно, так как первое, что известно в начале кодирования, — именно число разрядов информационных символов. Уравнение (1.4) дает тот же результат, что и (1.3).

Из (1.3) вытекает, что наиболее экономичными являются коды, для которых log₂(n +1) выражается целым числом, то есть когда длина кодовой комбинации

n = 2^m — 1,(1.5)

где m должно быть целым числом. Так, при k=11, n=15 и m=4 без всяких округлений. Но при k=12, n=17, так как m = 5 выбрано с округлением в сторону большего значения, что увеличивает избыточность кода: в первом случае И=4/15=0,266, во втором И=5/17=0,295.

2. Выбор образующего многочлена Р (Х). Степень образующего многочлена l не может быть меньше числа контрольных символов m. Это значит, что если m=3, то из табл. 1.1 можно выбрать любой образующий многочлен Р (Х) начиная с третьей степени и выше. Для упрощения технической реализации кодирования степень Р (Х) следует выбирать равной числу m, т. е. l=m. Если в таблице имеется ряд многочленов с данной степенью, то из них следует выбрать самый короткий. Однако число ненулевых членов многочлена Р (Х) не должно быть меньше кодового расстояния d.

3. Нахождение элементов дополнительной матрицы. Дополнительную матрицу находят путем деления единицы с нулями на выбранный многочлен R (X) и выписывания всех промежуточных остатков. При этом должны быть соблюдены следующие условия:

а) число остатков должно быть равно числу информационных символов k;

б) для дополнительной матрицы пригодны лишь остатки с весом W, не меньшим числа обнаруживаемых ошибок r, т. е. в данном случае не меньшим 2 (W?2); так обнаруживается не менее двух ошибок.

Из условий а) и б) определяется количество нулей, приписываемых к единице при делении ее на многочлен Р (Х);

в) так как элементы дополнительной матрицы являются для данной комбинации контрольными символами, то число разрядов дополнительной матрицы равно числу контрольных символов m. Вследствие того, что степень образующего многочлена выбирают равной m, число разрядов дополнительной матрицы равно также степени образующего многочлена. Например, если m=3, а остаток равен 11, то он должен быть записан как 011. Из сказанного вытекает, что разрядность остатка равна степени образующего многочлена.

4. Составление образующей матрицы. Берут транспонированную единичную матрицу и справа приписывают к ней элементы дополнительной матрицы. Пример составления образующей матрицы был дан при рассмотрении циклического кода с обнаружением одиночной ошибки.

5. Нахождение всех комбинаций циклического кода данной группы. Это достигается суммированием по модулю 2 всевозможных сочетаний строк образующей матрицы, как было показано при рассмотрении циклического кода с обнаружением одиночной ошибки.

Пример 1.2. Образовать циклический код, позволяющий обнаруживать двукратные ошибки или исправлять одиночную ошибку из всех комбинаций двоичного кода на все сочетания с числом информационных символов k = 4.

По уравнению (1.4) находим число контрольных символов:

m = Е" Iog₂ [(4 + 1) + E" log₂ (4 + 1)] = Е" Iog₂ (5 + 3)= 3.

Из табл.1.1 выбираем один из образующих многочленов третьей степени. Пусть Р (Х)=Х³ + Х + 1> 1011. Находим остатки от деления единицы с нулями на Р (Х), которые соответственно равны 011, 110, 111, 101. Остатков должно быть четыре согласно числу информационных символов. Выписывая транспонированную единичную матрицу и приписывая к ней справа матрицу дополнений в виде остатков, получаем образующую матрицу

Так как все члены единичной матрицы являются комбинациями заданного четырехразрядного двоичного кода, то четыре комбинации образующей матрицы представляют собой четыре комбинации требуемого циклического кода. Остальные 11 комбинаций циклического кода (начиная с пятой) могут быть получены путем суммирования по модулю 2 этих четырех комбинаций образующей матрицы так, как было проделано для кода с d=2:

5.

6.

7.

8.

9.

10.

11.

12.

13.

Заметим, что комбинация 13 была получена при выводе уравнения (1.2). Если сложить комбинации, то получим циклический код 1 011 000, в котором контрольными символами являются одни нули. Нулевая комбинация может быть также использована: у нее все символы — нули.

Как следует из табл. 1.1, в качестве образующего можно было бы взять и многочлен Р (Х)=Х³ + Х² + 1> 1101. В этом случае образующая матрица приняла бы вид

a₁1 101

a₂10 111

a₃100 011

a₄1 000 110

Многочлен Р (Х)=Х³ + Х + 1> 1011 называется обратным или двойственным многочленом многочлена Р (Х)=Х³ + Х² + 1> 1101. Действительно, сравнивая записанные в двоичной форме выражения обоих многочленов, видим, что нули и единицы в обратном многочлене расположены зеркально относительно основного многочлена, т. е. младший разряд становится старшим. Так, многочлен 1 110 101 является обратным многочлену 1 010 111. Двойственный многочлен можно записать в виде

Р*(Х)=Х^n-1Р (Х^-1). (1.6)

В нашем примере Р*(Х)= Х³(Х^-3 + Х^-2 + 1) = Х³ + Х + 1. Использование двойственных многочленов расширяет возможности построения циклических кодов, так как если Р (Х) — неприводимый многочлен, то и многочлен Р*(Х) также неприводим.

Циклическое кодирование можно осуществлять не только путем составления образующей матрицы из транспонированной матрицы и матрицы дополнения. Тот же результат достигается, если каждый из членов единичной транспонированной матрицы умножить на образующий многочлен. Так, если образующий многочлен Р (Х)=Х³ + Х + 1> 1011, то умножение транспонированной единичной матрицы на этот многочлен даст

0001X1011=1 011

0010Х1011=10 110

0100X1011=101 100

1000X1011=1 011 000

Заметим, что, например, умножение 0100X1011 эквивалентно 1011X X100=101 100. Нуль слева (101 100) приписывается для комплектности кода. Результатом умножения явился циклический сдвиг образующего многочлена. Сложением полученных комбинаций можно образовать те же комбинации, что и с помощью двух предыдущих образующих матриц.

Нами был выбран в качестве исходного четырехэлементный двоичный код на все сочетания (k = 4), что позволило образовать 2⁴=16 комбинаций циклического кода. Эти комбинации являются разрешенными, так как после кодирования разрядность кода из-за наличия контрольных символов m = 3 увеличилась до n = 7. Из 128 комбинаций семиразрядного двоичного кода 112 будут неразрешенными. При этом сравнение комбинаций, полученных с помощью образующей матрицы обоими многочленами, показывает, что из 32 комбинаций совпадают только нулевые и составленные из одних единиц.

Таким образом, из двоичного кода на все сочетания (k=4) были образованы два циклических кода с помощью различных образующих многочленов: Р (X)=1011 и P (X)=1101. При этом, несмотря на то что в каждом коде комбинации различны, оба кода вполне правомочны, так как комбинации в каждом из них отличаются друг от друга на кодовое расстояние d=3. В то же время сравнение кодов, составленных образующей матрицей [многочлен Р (Х)=Х³ + Х + 1] и умножением транспонированной матрицы на тот же многочлен, показывает полную идентичность комбинации этих кодов.

Теперь, когда ясна роль образующего многочлена при составлении циклических кодов, вырисовываются также следующие его свойства, которые могут помочь при изучении более сложных циклических кодов.

Первое свойство образующего многочлена заключается в том, что все разрешенные комбинации делятся на него без остатка. Это свойство следует из (1.2), и его можно проверить, разделив любую комбинацию кода на образующий ее многочлен. Таким образом, многочлен Р (Х) как бы позволяет образовать или выбрать из большего числа комбинации, удовлетворяющие только заданному закону построения кода, т. е. разрешенные. Поэтому многочлен Р (Х) и называется образующим.

Второе свойство образующего многочлена таково, что на него делится без остатка не только разрешенная комбинация, имеющая степень n — 1, но и двучлен Хⁿ + 1. В нашем примере n = 7. При делении числа 10 000 001 на 1011 получается частное 10 111 без остатка. Это значит, что образующий многочлен входит в качестве сомножителя в разложение двучлена Хⁿ + 1, который с учетом равенства (1.5) можно записать в виде. Так для двучлена составляющие сомножители разложения должны быть неприводимыми многочленами, степени которых являются делителями числа m = 3. К числам, на которые m = 3 делится без остатка, относятся 1 и 3. Из табл. 1.1 выпишем все неприводимые многочлены первой и третьей степеней, которые и явятся сомножителями в разложении двучлена Х⁷+1:

Х⁷+1= (Х+1)(Х³ + Х +1)(Х³ + Х² + 1)(1.7)

Один из неприводимых многочленов третьей степени и должен быть выбран для кодирования, если k=4. Заметим, что такое разложение двучлена Хⁿ+1 является одним из методов выбора образующего многочлена.

В рассмотренном примере при k=4 и m=3 n=k+m=7. В литературе циклические коды такого типа называются кодами (7,4). Из примера не следует, что для всех циклических кодов с обнаружением двойной ошибки образующий многочлен будет всегда иметь третью степень. Чем больше длина кода, тем выше степень образующего многочлена, что объясняется увеличением числа контрольных символов. Так, при k=26 согласно уравнению (1.4) m = 5. Это значит, что степень образующего многочлена должна быть не меньше пятой. Такой код обозначают как код (31,26).

Циклические коды с d=4. Эти коды могут обнаруживать одиночные, двойные и тройные ошибки или обнаруживать двойные и исправлять одиночные ошибки.

1. Выбор числа контрольных символов. Число контрольных символов в этом коде должно быть на единицу больше, чем для кода с d=3:

(1.8)

Для нахождения можно воспользоваться уравнением (1.4). Если число контрольных символов определяется, как в коде Хэмминга, то уравнение (1.3) примет вид

(1.9)

2. Выбор образующего многочлена. Образующий многочлен: равен произведению двучлена (Х+1) на многочлен

(1.10)

Это объясняется тем, что двучлен (Х+1) позволяет обнаружить все одиночные и тройные ошибки, а многочлен Р (Х) — двойные ошибки. Так, для кода (7,3), обнаруживающего все трехкратные ошибки, можно было бы выбрать .

В общем случае степень l многочлена равна числу m. Дальнейшая процедура кодирования остается такой же, как и при образовании кода с обнаружением двойной ошибки.

Пример 1.3. Требуется закодировать сообщение 10 101 010 101 010 циклическим кодом с d = 4:

G (X)= Х¹³ + Х¹¹ + Х⁹ + Х⁷ + Х⁵ + Х³+ Х >10 101 010 101 010.

Определяем число контрольных символов по уравнению (1.4):

Из уравнения (1.8) следует, что. Выбираем из табл. 1.1 образующий многочлен для d=3. Пусть. Тогда

Так как необходимо закодировать только одно сообщение G (X), а не весь ансамбль двоичных кодов с k=14, то будем придерживаться процедуры кодирования, выполняемой по уравнению (1.2). Выбираем одночлен. Тогда

Разделив полученное выражение на, находим остаток:

Следовательно, передаваемая закодированная комбинация будет иметь вид F (X) = (Х¹⁹ + Х¹⁷ + Х¹⁵ + Х¹³ + Х¹¹ + Х⁹ + Х⁷) + (Х⁴ + Х³ + Х² + X + 1) .

10 101 010 101 010 11 111

Информационные Контрольные

символы символы

1.2.5 Методы декодирования циклических кодов и обнаружения ошибок

Обнаружение ошибок. Идея обнаружения ошибок в принятом циклическом коде заключается в том, что при отсутствии ошибок закодированная комбинация F (X) делится на образующий многочлен Р (Х) без остатка. При этом контрольные символы m отбрасываются, а информационные символы k используются по назначению. Если произошло искажение принятой комбинации, то эта комбинация F (X) преобразуется в комбинацию Н (Х), которую можно представить как сумму двух многочленов:

H (X)=F (X) + E (X),(1.11)

где Е (Х)—многочлен ошибок, содержащий столько единиц, сколько элементов в принятой комбинация не совпадает с элементами переданной комбинации.

Пусть, например, была передана комбинация кода (7,4) ==1 101 001, закодированная с помощью Р (Х)=1011. Если она принята правильно, то деление на Р (Х) даст остаток, равный нулю. Если же комбинация принята как Н (Х)=1 101 011, то при делении на Р (Х) образуется остаток 010, что свидетельствует об ошибке, и принятая комбинация бракуется.

Обнаружение и исправление ошибок. Существует несколько вариантов декодирования циклических кодов. Один из них заключается в следующем.

1. Вычисление остатка (синдрома). Так же как и в кодах с обнаружением ошибок, принятую комбинацию делят на образующий многочлен Р (Х). Остаток R (X)=0 означает, что комбинация принята без ошибок. Наличие остатка свидетельствует о том, что комбинация принята искаженной. Дальнейшая процедура исправления ошибок протекает таким образом.

2. Подсчет веса остатка W. Если вес остатка равен или меньше числа исправляемых ошибок, т. е., то принятую комбинацию складывают по модулю 2 с остатком и получают исправленную комбинацию.

3. Циклический сдвиг на один символ влево. Если W>s, то производят циклический сдвиг на один символ влево и полученную комбинацию снова делят на образующий многочлен. Если вес полученного остатка, то циклически сдвинутую комбинацию складывают с остатком и затем циклически сдвигают ее в обратную сторону вправо на один символ (возвращают на прежнее место). В результате получают исправленную комбинацию.

4. Дополнительные циклические сдвиги влево. Если после циклического сдвига на один символ по-прежнему W>s, то производят дополнительные циклические сдвиги влево. При этом после каждого сдвига сдвинутую комбинацию делят на Р (Х) и проверяют вес остатка. При выполняют действия, указанные в п. 3, с той лишь разницей, что обратных циклических сдвигов вправо делают столько, сколько их было сделано влево.

Пример 1.4. Принят код 1 101 110, закодированный образующим многочленом Р (Х)=1011 и с s = l. Проверить наличие ошибки и в случае обнаружения исправить ее.

Делим комбинацию 1 101 110 на 1011 и находим, что остаток R (X)=111. Так как это не удовлетворяет равенству W=s, сдвигаем комбинацию 1 101 110 циклически на один символ влево. Получаем 1 011 101. В результате деления этой комбинации на Р (Х) находим остаток R1(X)=101. Вес этого остатка равен двум, т. е. больше s. Осуществляем новый циклический сдвиг влево. Получаем 111 011. Деление на Р (Х) дает остаток R2(X)=001, вес которого равен s. Складываем: 111 011 001 = 111 010. Теперь осуществляем два циклических сдвига последней комбинации вправо: после первого она принимает вид 11 101, после второго — 1 001 110, т. е. получается уже исправленная комбинация. Проверка показывает, что эта комбинация делится на Р (Х) без остатка.

1.3 Математическая модель

Исходя из технического задания d = 4, а согласно формуле

d = r + s + 1, где