Составление таблицы опознавателей
Лабораторная работа N 3
ПОСТРОЕНИЕ ГРУППОВЫХ КОДОВ
Целью работы является усвоение принципов построения групповых корректирующих кодов.
Указания к построению кодов
Определение числа избыточных символов
Групповой код относится к блоковым кодам, в которых формируемая кодовая комбинация содержит n разрядов, из которых k–информационных и m– проверочных ( m = n - k ). Взаимосвязь между блоками отсутствует, то есть передача и исправление ошибок в разных блоках происходят независимо друг от друга. Математической основой группового кода является теория групп (отсюда и название кода). В качестве основной операции в групповых кодах используется операция сложения по модулю два.
Построение конкретного корректирующего кода производится исходя из числа передаваемых букв (команд) или дискретных значений измеряемой величины, то есть алфавита из N элементов и статистических данных о наиболее вероятных векторах ошибок в используемом канале связи. Вектором ошибки будем называть кодовую комбинацию, имеющую единицу в разрядах, подвергающихся искажению, и нули во всех остальных разрядах. Любую искаженную кодовую комбинацию можно рассматривать теперь как сумму по модулю два разрешенной кодовой комбинации и вектора ошибки.
Будем рассматривать как независимые ошибки, так и пачки ошибок. Независимые ошибки, это когда по одной из них ничего нельзя сказать о других. В пачках ошибки расположены рядом. Длиной пачки ошибки называется дистанция между первым и последним искаженным символом. Внутри пачки могут оказаться и неискаженные символы.
|
|
|
Исходя из неравенства 
, определяем число информационных разрядов k, необходимое для передачи заданного числа команд обычным двоичным кодом.
Каждой из 
ненулевых комбинаций К-разрядного кода нам необходимо поставить в соответствие комбинацию из n разрядов. Значения символов в n–к проверочных разрядах такой комбинации устанавливаются в результате суммирования по модулю два значений символов в определенных информационных разрядах.
Нам надлежит определить число проверочных разрядов, их значение и местоположение в n-разрядной кодовой комбинации.
Из общего числа 
возможных ошибок, групповой код может исправить всего 
разновидностей ошибок.
Чтобы иметь возможность получить информацию о векторе ошибки, воздействию которого подверглась полученная кодовая комбинация, каждому вектору ошибки, подлежащей устранению, должна быть сопоставлена некоторая контрольная последовательность символов, называемая опознавателем.
Каждый символ опознавателя будет определяться в результате проверки одного из равенств на приемной стороне. Эти равенства мы составим для определения значений проверочных символов при кодировании на передающей стороне.
|
|
|
В групповом коде значения проверочных символов подбираются так, чтобы сумма по модулю два всех символов (включая проверочный), входящих в каждое из равенств, равнялась нулю. В таком случае число единиц среди этих символов при отсутствии ошибок четное. Поэтому операции определения символов опознавателя называют проверками на четность. При отсутствии ошибок в результате всех проверок на четность образуется опознаватель, состоящий из одних нулей. Если проверочное равенство не удовлетворяется, то в соответствующем разряде опознавателя появляется единица. Исправление ошибок возможно лишь при наличии взаимно однозначного соответствия между множеством опознавателей и множеством подлежащих исправлению разновидностей ошибок.
Таким образом, количество подлежащих исправлению ошибок является определяющим для выбора числа избыточных разрядов n-к. Последних должно быть достаточно для того, чтобы обеспечить необходимое число опознавателей.
Если, например, мы желаем исправлять все одиночные ошибки, то исправлению подлежит n ошибок. Вектора ошибок имеют в этом случае следующий вид :
|
|
|
 =(000...01)  =(000...10)
........
 =(100...00)
|
Различных ненулевых опознавателей должно быть не менее n.
Необходимое число проверочных разрядов, следовательно, должно определяться из соотношения :
.
В общем случае для исправления всех независимых ошибок кратности до t включительно получаем :
.
В общем случае это неравенство записывается следующим образом: 
, где Q число ошибок, которые необходимо исправить. Например, для исправления пачек в 3 и менее символов
, где
n – одиночные ошибки,
( n -1) – пачки в 2 соседних символа (… 0110…)
2( n -2) – пачки в 3 соседних символа (…01110…) и в два символа через один (…01010…).
Стоит подчеркнуть, что в приведенных соотношениях указывается теоретический предел минимально возможного числа проверочных разрядов, который далеко не во всех случаях можно реализовать практически.
Составление таблицы опознавателей
Начнем для простоты с установления опознавателей для случая исправления одиночных ошибок. Допустим, необходимо закодировать 15 команд (букв).
Таблица 2.1
| N разряда | Вектор ошибки | Опознаватель |
| 1 2 3 4 5 6 7 | 0000001 0000010 0000100 0001000 0010000 0100000 1000000 | 001 010 011 100 101 110 111 |
|
|
|
Тогда к=4, n=7. Три избыточных разряда позволяют использовать в качестве опознавателей трехразрядные двоичные последовательности. В принципе они могут быть сопоставлены подлежащим исправлению ошибкам в любом порядке. Однако, более целесообразно опознаватели сопоставлять с номерами разрядов, в которых произошли ошибки (табл. 2.1).
Коды, в которых опознаватели устанавливаются по указанному принципу, известны как коды Хэмминга.
Возьмем теперь более сложный случай исправления всех одиночных и двойных независимых ошибок, то есть две ошибки в любых разрядах. В качестве опознавателей одиночных ошибок в первом и втором разрядах можно принять, как и ранее две комбинации 0...001 и 0...010 (табл. 2.2).
Подлежащий исправлению вектор ошибки 0...011 может рассматриваться как результат суммарного воздействия двух векторов ошибок 0...010 и 0...001 и, следовательно, ему должен быть сопоставлен опознаватель, представляющий собой сумму по модулю два опознавателей этих ошибок, т.е. 0...011.
Вектору ошибки 0...0100 сопоставляем опознаватель 0...0100 и т.д. Выбирая в качестве опознавателя единичной ошибки в i-м разряде комбинацию с числом разрядов меньшим i, необходимо убедиться в том, что для всех остальных подлежащих исправлению векторов ошибок, имеющих единицы в i-м и более младших разрядах, получаются опознаватели, отличные от уже использованных. В результате имеем:
Таблица 2.2
| Вектор ошибки | Опознаватель | Вектор ошибки | Опознаватель |
| 00000001 00000010 00000011 00000100 00000101 00000110 00001000 00001001 | 000001 000010 000011 000100 000101 000110 001000 001001 | 00001010 00001100 00010000 00010001 00010010 00010100 00011000 00100000 | 001010 001100 001111 001110 001101 001011 000111 010000 |
Таким путем можно получить таблицу опознавателей для векторов ошибок в любом числе разрядов.
Если опознаватели векторов ошибок с единицами в нескольких разрядах устанавливаются как суммы по модулю два опознавателей одиночных ошибок в этих разрядах, то для определения проверочных равенств достаточно знать только опознаватели одиночных ошибок в каждом из разрядов.
Для построения кодов, исправляющих двойные независимые ошибки, пачки ошибок в двух и трех разрядах опознаватели одиночных ошибок в каждом из разрядов сведены в табл. 2.3, 2.4, 2.5, которые составлены с помощью ЭВМ.
| Таблица 2.3 Опознаватели одиночных ошибок для кода, исправляющий двойные независимые ошибки | Таблица 2.4 Опознаватели одиночных ошибок для кода, исправляющего пачки ошибок в двух и менее разрядов |
| N разряда | Опознаватель |
| N разряда | Опознаватель |
| 1 2 3 4 5 6 7 8 9 | 0000001 0000010 0000100 0001000 0001111 0010000 0100000 0110011 1000000 | 1 2 3 4 5 6 7 8 | 00001 00010 00100 01000 01101 00111 01110 10000 |
Таблица 2.5 Опознаватели одиночных ошибок для кода, исправляющего пачки ошибок в трех и менее разрядах
| N разряда | Опознаватель |
| 1 2 3 4 5 6 7 8 9 10 | 0000001 0000010 0000100 0001000 0010000 0100000 0001001 0010010 0100100 1000000 |
Дата добавления: 2021-03-18; просмотров: 637; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!