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

6.6.2. Пример кода (n, k)

6.6.3. Разработка кода (8, 2)

6.6.4. Соотношение между обнаружением и исправлением ошибок

6.6.5. Взгляд на код сквозь нормальную матрицу

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

6.6.2. Пример кода (n, k)

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

Для получения нетривиального соотношения между исправлением и обнаружением ошибок желательно, чтобы код имел возможности коррекции ошибок, по крайней мере, с t = 2. Согласно уравнению (6.44), минимальное расстояние при этом равно .

Чтобы кодовая система была нетривиальной, желательно, чтобы количество бит данных было не менее k = 2. Следовательно, число кодовых слов . Далее будем считать наш код следующим: (п, 2).

Нас интересует минимальное значение п, которое позволит исправлять все одно- и двухбитовые ошибки. В этом примере каждый из n-кортежей в матрице будет табулирован. Минимальное значение n нас интересует потому, что при каждом увеличении n на единицу число n-кортежей в нормальной матрице удваивается. Это условие, разумеется, диктуется только соображениями удобства использования таблицы. Для реальных прикладных кодов минимальное значение n выбирается по разнымпричинам—эффективность использования полосы пропускания и простота системы. Если при выборе n используется предел Хэмминга, то n следует выбрать равным 7. В то же время размерность полученного кода (7,2) не соответствует указанным выше требованиям t = 2 и . Чтобы увидеть это, следует ввести другую верхнюю границу возможностей кода в коррекции t-битовых ошибок (или ) Эта граница, называемая предел Плоткина [7], определяется следующим образом.

(6.54)

Вообще, линейный код (n, k) должен удовлетворять всем перечисленным выше условиям, включая возможности коррекции ошибок (или минимальное расстояние). Для высокоскоростных кодов из удовлетворения предела Хэмминга следует удовлетворение предела Плоткина; это справедливо, например, для рассмотренного ранее кода (127,106). Для кодов с низкими скоростями передачи существует обходной путь удовлетворения названных требований [7]. Поскольку в нашем примере речь идет именно о таких кодах, важно оценить их возможности в коррекции ошибок с помощью предела Плоткина. Поскольку , из уравнения (6.53) получаем, что n должно быть равно 8; следовательно, для удовлетворения всех требований, поставленных в этом примере, минимальная размерность кода равна (8,2). Можно ли практически использовать подобный код (8,2)? Этого делать не стоит, поскольку это потребует слишком большой полосы пропускания; лучше выбрать более эффективный код. Данный код мы используем только с методической целью, единственным его преимуществом являются удобные размеры его нормальной матрицы.

6.6.3. Разработка кода (8, 2)

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

1. Количество кодовых слов .

2. Среди кодовых слов должен быть нулевой вектор.

3 Следует учесть свойство замкнутости — сумма двух любых кодовых слов в пространстве должна давать кодовое слово из этого же пространства.

4. Каждое кодовое слово содержит 8 двоичных разрядов.

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

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

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

Сообщения Кодовые слова

00

00000000

01

11110001

10

00111110

11

11001111

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

6.6.4. Соотношение между обнаружением и исправлением ошибок

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

Декодирование начинается с расчета синдрома, что можно представлять как изучение "симптомов" ошибки. Для кода (п, k) -битовый синдром S является произведением принятого n-битового вектора r и транспонированной проверочной матрицы Н размерностью . Проверочная матрица Н построена таким образом, что строки матрицы G ортогональны строкам матрицы Н, т.е.. В нашем примере кода (8, 2) S — это 6-битовый вектор, а Н — матрица размером 6 х 8, где

Синдром для каждой ошибочной комбинации можно рассчитать, исходя из уравнения (6.37), а именно

,

где — один из синдромов, а — один из 64 образующих элементов классов смежности (ошибочных комбинаций) в нормальной матрице. На рис. 6.15, помимо самой нормальной матрицы, показаны все 64 синдрома для кода (8, 2). Набор синдромов рассчитывался с помощью уравнения (6.37); позиции произвольной строки (смежный класс) нормальной матрицы имеют один и тот же синдром. Исправление искаженного кодового слова осуществляется путем расчета его синдрома и локализации ошибочной комбинации, соответствующей этому синдрому. В заключение ошибочная комбинация прибавляется (по модулю 2) к поврежденному кодовому слову, что и дает правильное кодовое слово. Из уравнения (6.49), повторно приведенного ниже, видно, что между возможностями обнаружения и исправления ошибок существует некий компромисс, ограничиваемый расстоянием.

Здесь представляет количество исправляемых битовых ошибок, а — количество обнаруживаемых битовых ошибок, причем . В коде (8,2) возможны следующие компромиссы между этими двумя величинами.

Обнаружение Исправление

2

2

3

1

4

0

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

Для исправления однобитовых ошибок декодер может реализовываться с логическими элементами [4], подобными приведенным на рис. 6.12, где принятый вектор кода поступал в схему в двух точках. В верхней части рисунка принятые символы поступают на логический элемент исключающего ИЛИ, который и определяет синдром. Для любого принятого вектора синдром рассчитывается согласно уравнению (6.35).

000000 1. 00000000 11110001 00111110 11001111
111100 2. 00000001 11110000 00111111 11001110
001111 3. 00000010 11110011 00111100 11001101
000001 4. 00000100 11110101 00111010 11001011
000010 5. 00001000 11111001 00110110 11000111
000100 6. 00010000 11100001 00101110 11011111
001000 7. 00100000 11010001 00011110 11101111
010000 8. 01000000 10110001 01111110 10001111
100000 9. 10000000 01110001 10111110 01001111
110011 10. 00000011 11110010 00111101 11001100
111101 11. 00000101 11110100 00111011 11001010
111110 12. 00001001 11111000 00110111 11000110
111000 13. 00010001 11100000 00101111 11011110
110100 14. 00100001 11010000 00011111 11101110
101100 15. 01000001 01110000 01111111 10001110
011100 16. 10000001 11110111 10111111 01001110
001110 17. 00000110 11111011 00111000 11001001
001101 18. 00001010 11111011 00110100 11000101
001011 19. 00010010 11100011 00101100 11011101
000111 20. 00100010 11010011 00011100 11101101
011111 21. 01000010 10110011 01111100 10001101
101111 22. 10000010 01110011 10111100 01001101
000011 23. 00001100 11111101 00110010 11000011
000101 24. 00010100 11100101 00101010 11011011
001001 25. 00100100 11010101 00011010 11101011
010001 26. 01000100 10110101 01111010 10001011
100001 27. 10000100 01110101 10111010 01001011
000110 28. 00011000 11101111 00001110 11010111
001010 29. 00101000 11011001 00010110 11100111
010010 30. 01001000 10111001 01110110 10000111
100010 31. 10001000 01111001 10110110 01000111
001100 32. 00110000 01000001 00001110 11111111
010100 33. 01010000 10100001 01101110 10011111
100100 34. 10010000 01100001 10101110 01011111
011000 35. 01100000 10010001 01011110 10101111
101000 36. 10100000 01010001 10011110 01101111
110000 37. 11000000 00110001 11111110 00001111
110010 38. 00000111 11100010 00111001 01101000
110111 39. 00010011 11100010 00101101 11011100
111011 40. 00100011 11010010 00011101 11101100
100011 41. 01000011 10110010 01111101 10001100
010011 42. 11000011 01110010 10111101 01001100
111111 43. 10000011 11111100 00110011 11000010
111001 44. 00010101 11100100 00101011 11011010
110101 45. 00100101 11010100 00011011 11101010
101101 46. 01000101 10110100 01111011 10001010
011101 47. 10000101 01110100 10111011 01001010
011110 48. 01000110 10110111 01111000 10001001
101110 49. 10000110 01110111 10111000 01001001
100101 50. 10010100 01100101 10101010 01011011
011001 51. 01100100 10010101 01011010 10101011
110001 52. 11000100 00110101 11111010 00001011
011010 53. 01101000 10011001 01010110 10100111
010110 54. 01011000 10101001 01100110 10010111
100110 55. 10011000 01101001 10100110 01010111
101010 56. 10101000 01011001 10010110 01100111
101001 57. 10100100 01010101 10011010 01101011
100111 58. 10100010 01010011 10011100 01101101
010111 59. 01100010 10010011 01011100 10101101
010101 60. 01010100 10100101 01101010 10011011
011011 61. 01010010 10100011 01101100 10011101
110110 62. 00101001 11011000 00010111 11100110
111010 63. 00011001 11101000 00100111 11010110
101011 64. 10010010 01100011 10101100 01011101

Рис. 6.15. Синдромы и нормальная матрица для кода(8, 2)

С помощью значений Нгдля кода (8,2), необходимо так соединить элементы схемы (подобно тому, как это было сделано на рис. 6.12), чтобы вычислялось следующее.

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

Для реализации схемы декодера для кода (8,2), подобной представленной на рис. 6.12, необходимо, чтобы восемь принятых разрядов соединялись с шестью сумматорами по модулю 2 (см. выше), выдающими цифры синдрома. Соответственно, потребуются и другие модификации схемы, приведенной на рисунке.

Если декодер реализован так, чтобы исправлять только однобитовые ошибки (т.е. ), это эквивалентно ограничению матрицы на рис. 6.15 девятью первыми классами смежности, а исправление ошибок происходит, только когда один из восьми синдромов соответствует появлению однобитовой ошибки. Затем схема декодирования (подобная изображенной на рис. 6.12) преобразует синдром в соответствующую ошибочную комбинацию. Далее ошибочная комбинация прибавляется по модулю 2 к "потенциально" искаженному принятому вектору, т.е. происходит исправление ошибки. Для проверки ситуаций, когда синдром не равен нулю, а схемы коррекции нет, нужно вводить дополнительные логические элементы (например, для однобитовых ошибок, соответствующих синдромам 10-64).

Если декодер реализован так, чтобы исправлять одно- и двухбитовые ошибки (а это означает, что обнаруживается, а затем исправляется ошибки), это эквивалентно ограничению матрицы (рис. 6.15) 37 классом смежности. Хотя код (8,2) может исправлять некоторые комбинации трехбитовых ошибок, соответствующие образующим элементам классов смежности под номерами 38-64, декодер чаще всего реализуется как декодер с ограниченным расстоянием; это означает, что он исправляет все искаженные символы, содержащие ошибку только в t или меньшем числе бит. Нереализованные возможности используются для некоторого улучшения процесса обнаружения ошибок. Как и ранее, реализация декодера подобна схеме, изображенной на рис. 6.12.

6.6.5. Взгляд на код сквозь нормальную матрицу

В контексте рис. 6.15 код (8,2) удовлетворяет пределу Хэмминга. Иными словами, из нормальной матрицы можно видеть, что код (8,2) способен исправлять все комбинации одно- и двухбитовых ошибок. Рассмотрим следующее: пусть передача происходит по каналу, который всегда вносит ошибки в виде пакета 3-битовых ошибок, и, следовательно, нет необходимости в исправлении одно- или двухбитовых ошибок. Можно ли настроить образующие элементы классов смежности так, чтобы они соответствовали только трехбитовым ошибкам? Нетрудно определить, что в последовательности из 8 бит существует возможностей произвести трехбитовую ошибку. Если единственным нашим желанием является коррекция только этих 56 комбинаций трехбитовых ошибок, то кажется, что в нормальной матрице достаточно места (достаточное количество классов смежности), поскольку всего в ней имеется 64 строки. Будет ли это работать? Однозначно, нет. Для любого кода главным параметром, определяющим способности кода к коррекции ошибок, является . Для кода (8, 2) , а это означает, что возможно исправление только 2-битовых ошибок.

Как стандартная матрица может помочь разобраться, почему эта схема не будет работать? Чтобы осуществить исправление x-битовых ошибок для группы x-битовых ошибочных комбинаций, полная группа векторов с весовым коэффициентом х должна быть классом смежности, т.е. они должны находиться только в крайнем левом столбце. На рис. 6.15 можно видеть, что все векторы с весовым коэффициентом 1 и 2 находятся в крайнем левом столбце нормальной матрицы и нигде более. Если мы даже и втиснем все векторы с весовым коэффициентом 3 в строку со второго номера по 57-й, увидим, что некоторые из этих векторов снова появятся в матрице где-нибудь еще (что нарушит основное свойство нормальной матрицы). На рис. 6.15 затененные блоки обозначают те 56 векторов, которые имеют весовой коэффициент 3. Взгляните на образующие элементы классов смежности, представляющие 3-битовые ошибочные комбинации, в строках 38, 41-43, 46-49 и 52 нормальной матрицы. Потом посмотрите на позиций в тех же строках в крайнем правом столбце, где затененные блоки показывают другие векторы с весовым коэффициентом 3. Видите некоторую неопределенность, существующую для каждой строки, о которых говорилось выше, и понятно ли теперь, почему нельзя исправить все 3-битовые ошибочные комбинации с помощью кода (8,2)? Допустим, декодер принял вектор с весовым коэффициентом 3 — 11001000, размещенный в строке 38 в крайнем правом столбце. Это искаженное кодовое слово могло появиться, во-первых, при передаче кодового слова 1 1 0 0 1 1 1 1, искаженного 3-битовой ошибочной комбинацией 0 0 0 0 0 1 1 1, а во-вторых, при передаче кодового слова 00000000, искаженного 3-битовой ошибочной комбинацией 1 1 0 0 1 0 0 0.