 Популярные статьи | |
| Сейчас на сайте |  Гостей: 1
На сайте нет зарегистрированных пользователей
Пользователей: 9,955
новичок: Logyattella
|
|
| 2.4.5 Построение двоичного группового кода |
Построение конкретного корректирующего кода производят, исходя из требования объёма кода Q , то есть необходимого числа передаваемых кодовых комбинаций и статистических данных о наиболее вероятных ошибках в используемом канале связи. Ошибки, возникающие в канале связи, описываются вектором ошибки – n- разрядным двоичным вектором, имеющем единицы в разрядах, подвергающихся искажению, и нули во всех остальных разрядах.
Любую искажённую кодовую комбинацию можно рассматривать при этом как сумму по модулю два неискажённой кодовой комбинации и вектора ошибки. Число информационных разрядов k, необходимое для передачи заданного числа комбинаций при обычном не избыточном кодировании может быть найдено как 2k Q.
Каждой из 2k комбинаций к – разрядного без избыточного кода необходимо поставить в соответствие комбинацию из n – символов. Значения символов в n – k проверочных разрядах устанавливаются в результате суммирования по модулю два значений символов в определённых информационных разрядах. Поскольку множество 2k комбинаций информационных символов образует подгруппу группы всех n-разрядных комбинаций, то и множество разрешённых комбинаций, построенных по определенному правилу, тоже является подгруппой группы всех n-разрядных комбинаций. Это множество и будет групповым кодом.
Для полного построения кода необходимо определить число проверочных разрядов и номера информационных разрядов, входящих в каждое из равенств для определения символов в проверочных разрядах.
Если разложить группу 2n всех комбинаций на смежные классы по подгруппе 2к разрешённых n – разрядных комбинаций, то помимо самой подгруппы кода в разложении будет насчитываться 2n-k –1 смежных классов. Элементы каждого класса представляют собой суммы по модулю 2 комбинаций кода и образующих элементов данного класса. Если за образующие элементы каждого класса принять те наиболее вероятные для заданного канала векторы ошибки, которые должны быть исправлены, то в каждом смежном классе сгруппируются кодовые комбинации, получающиеся в результате воздействия на все разрешённые комбинации определённого вектора ошибки.
Для исправления любой полученной на выходе кодовой комбинации теперь достаточно определить, к какому классу смежности она относится. Складывая её затем по модулю 2 с образующим элементов данного класса смежности, получаем истинную комбинацию кода. Общее число ошибок, которые может исправлять групповой код, равно 2n-k –1 по числу классов смежности. Чтобы иметь возможность получить информацию о том, к какому смежному классу относится полученная комбинация, каждому смежному классу должна быть поставлена в соответствие некоторая контрольная последовательность символов, называемая опознавателем, или синдромом.
Каждый символ опознавателя определяется в результате проверки на приёмной стороне справедливости одного из равенств, которые мы составляем для определения значений проверочных символов при кодировании.
В двоичном линейном коде значения проверочных символов выбирают так, чтобы сумма по модулю 2 всех символов (включая проверочные), входящих в каждое из равенств, равнялись нулю. Таким образом, при отсутствии ошибки в результате всех проверок на чётность в равенствах образуется опознаватель, состоящий из одних нулей. Если проверочное равенство не удовлетворяется, то в соответствующем разряде опознавателя появляется 1. Исправление ошибок возможно лишь при наличии взаимно однозначного соответствия между множеством опознавателей и множеством смежных классов, а следовательно, и множеством подлежащих исправлению векторов ошибки. Если необходимо исправить все одиночные ошибки, то исправлению подлежат n ошибок. Различных не нулевых опознавателей должно быть не менее n. Необходимое число проверочных разрядов, следовательно, должно определяться из соотношения:
, (2.4.11)
или
. (2.4.12)
Если необходимо исправить не только все единичные, но и все двойные независимые ошибки, то соответствующие неравенства принимают вид:
. (2.4.13)
В общем случае для исправления всех независимых ошибок кратности s получаем:
. (2.4.14)
Приведённые соотношения определяют теоретический предел минимально возможного числа проверочных символов, который далеко не во всех случаях можно реализовать практически. Часто требуется большее количество проверочных символов.
Рассмотрим теперь процесс составления таблицы опознавателей. Начнём для простоты с установления опознавателей для случая исправления одиночных ошибок. Допустим, что необходимо закодировать 15 кодовых комбинаций. требуемое число информационных разрядов равно четырём. Пользуясь соотношением: 2n-k –1 = n, определяем общее число разрядов кода а, следовательно, и число ошибок, подлежащих исправлению (n=7). Три избыточных разряда позволяют использовать в качестве опознавателей трёхразрядные двоичные последовательности. Ненулевые последовательности в принципе могут быть сопоставлены с подлежащими исправлению ошибками в любом порядке, однако более целесообразно сопоставлять их с ошибками в разрядах, начиная с младшего, в порядке возрастания двоичных чисел (см. табл. 2.1 и 2.2).
Таблица 2.1
Векторы
ошибки Опознаватели Векторы
ошибки Опознаватели
0000001 001 0010000 101
0000010 010 0100000 110
0000100 011 1000000 111
0001000 100
Коды, в которых опознаватели указывают номер разряда, в котором произошла ошибка, известны как коды Хэмминга. Таким образом, для любого кода, имеющего целью исправлять наиболее вероятные векторы ошибок заданного канала связи, можно составить таблицу опознавателей одиночных ошибок в каждом из разрядов. Пользуясь этой таблицей, нетрудно определить, символы каких разрядов должны входить в каждую из проверок на чётность.
Рассмотрим составление групп разрядов для варианта n=7, k=4.
Таблица 2.2
Номер
разряда Опознаватель Номер
разряда Опознаватель Номер
разряда Опознаватель
1 0001 7 0111 13 1101
2 0010 8 1000 14 1110
3 0011 9 1001 15 1111
4 0100 10 1010 16 10000
5 0101 11 1011
6 0110 12 1100
Предположим, что в результате первой проверки на чётность для младшего разряда опознавателя будет получена 1. Очевидно, что возможно при ошибке в одном из разрядов, опознаватели которых в младшем разряде имеют единицу. Следовательно, первое проверочное равенство должно включать 1, 3, 5 и 7 разряды.
Единица во втором разряде опознавателя может быть в следствии ошибки в разрядах, опознаватели которых имеют единицу во втором разряде. Отсюда второе равенство должно состоять из 2, 3, 6 и 7 разрядов. Аналогично третье равенство состоит из 4, 5, 6 и 7 разрядов. В качестве проверочных разрядов мы должны выбирать номера тех разрядов, которые входят только в одно из проверочных равенств. Это обеспечит однозначное определение значений символов в проверочных разрядах при кодировании. Указанному условию соответствуют разряды, опознаватели которых имеют по одной единице. В нашем случае это будут первый, второй и четвёртый разряды. Таким образом для выбранного примера, искомые правила построения кода, реализуемые в процессе кодирования, принимают вид:
, (2.4.15)
, (2.4.16)
. (2.4.17)
Поскольку построенный код имеет минимальное Хеммингово расстояние dmin = 3, он может использоваться с целью обнаружения единичных и двойных ошибок. Для обнаружения двойных ошибок необходимо получить сумму двух опознавателей единичных ошибок. Такое суммирование даёт не нулевой результат. Получается новый опознаватель двойной ошибки, что и является признаком наличия ошибки.
|
|
| Комментарии |
| Добавить комментарий |
|
Пожалуйста залогиньтесь для добавления комментария.
|
| Рейтинги |
|
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
|
|
| Гость |
Вы не зарегистрированны? Нажмите здесь для регистрации.
Забыли пароль? Запросите новый здесь.
|
| Мини-чат | Вам необходимо залогиниться.
Нет присланных сообщений.
|
|
