Лекции по Теоретическим основам цифровой связи   

6. Канальное кодирование: часть 1

6.6. Полезность нормальной матрицы

6.6.1. Оценка возможностей кода

Нормальную матрицу можно представлять как организационный инструмент, картотеку, содержащую все возможные  записи в пространстве n-кортежей, в которой ничего не упущено и не продублировано. На первый взгляд может показаться, что выгода от использования этого инструмента ограничена малыми блочными кодами, поскольку для кодов длиной более n=20 пространство n-кортежей насчитывает миллионы элементов. Впрочем, даже для больших кодов нормальная матрица позволяет определить важные исходные характеристики, такие как возможные компромиссы между обнаружением и исправлением ошибок и пределы возможностей кода в коррекции ошибок. Одно из таких ограничений, называемое пределом Хэмминга [7], описывается следующим образом.

Количество бит четности:         (6.52,а)

или

Количество классов смежности:       (6.52,6)

Здесь величина , определяемая уравнением (6.16), представляет число способов выбора из п бит j ошибочных. Заметим, что сумма членов уравнения (6.52), находящихся в квадратных скобках, дает минимальное количество строк, которое должно присутствовать в нормальной матрице для исправления всех комбинаций ошибок, вплоть до t-битовых ошибок. Неравенство определяет нижнюю границу числа п-k бит четности (или  классов смежности) как функцию возможностей кода в коррекции t-битовых ошибок. Аналогичным образом можно сказать, что неравенство дает верхнюю границу возможностей кода в коррекции t-битовых ошибок как функцию числа n-k бит четности (или  классов смежности). Для обеспечения возможности коррекции t-битовых ошибок произвольных линейных блочных кодов (п, k) необходимым условием является удовлетворение предела Хэмминга.

Чтобы показать, как нормальная матрица может обеспечить визуальное представление этого предела, возьмем в качестве примера код БХЧ (127,106). Матрица содержит все = 2127= 1,70 х 1038n- кортежей пространства. Верхняя строка матрицы содержит = 2106 = 8,11 x 1031 кодовых слов; следовательно, это число столбцов в матрице. Крайний левый столбец содержит 2 097 152  образующих элемента классов смежности; следовательно, это количество строк в матрице. Несмотря на то что число n-кортежей и кодовых слов просто огромно, нас не интересует конкретный вид каждого элемента матрицы. Основной интерес представляет количество классов смежности. Существует 2 097 152 класса смежности и, следовательно, 2 097 151 ошибочная комбинация, которую способен исправить, этот код. Далее показано, каким образом это число классов смежности определяет верхний предел возможностей кода в коррекции t-битовых ошибок.

Поскольку каждое кодовое слово содержит 127 бит, существует 127 возможностей допустить ошибку в одном бите. Рассчитываем количество возможностей появления двух ошибок —  = 8 001. Затем переходим к трехбитовым ошибкам, поскольку ошибки, упомянутые выше, — это лишь незначительная часть всех 2 097 151 ошибочных комбинаций. Итак, существует  = 333 375 возможностей совершить трехбитовую ошибку.

Эти расчеты приведены в табл. 6.3; там же показано, что нулевая ошибочная комбинация требует наличия первого класса смежности. Затем перечислены требования одно-, двух- и трехбитовых ошибок. Также показывается количество классов смежности, необходимое для коррекции каждого типа ошибок, и общее количество классов смежности, необходимых для коррекции ошибок всех типов, вплоть до требуемого типа ошибки. Из этой таблицы можно видеть, что код (127,106) способен исправить все комбинации, содержащие 1, 2 или 3 ошибочных бита, причем это составляет только 341504 из 2 097 152 возможных классов смежности. Неиспользованные 1 755 648 строк говорят о больших потенциальных возможностях в коррекции ошибок, чем было использовано. Действительно, в матрицу можно попытаться втиснуть все возможные 4-битовые ошибки. Но при взгляде на табл. 6.3 становится совершенно ясно, что это невозможно, поскольку, как показывает последняя строка таблицы, число оставшихся в матрице классов смежности значительно меньше общего числа классов смежности, требуемого для коррекции 4-битовых ошибок. Следовательно, предел Хэмминга описанного кода (127,106) гарантирует исправление всех ошибок вплоть до 3-битовых.

Таблица 6.3. Предел возможностей коррекции для кода (127, 106)

Количество битовых ошибок  Количество необходимых        Общее число необходимых

                                                       классов смежности                    классов смежности

0

1

1

1

127

128

2

8001

8129

3

333375

341504

4

10334625

10676129



*****
© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.