8.1.7. Границы для минимальных расстояний линейных блоковых кодов

Выражения для вероятности ошибки, полученные в этой главе для декодирования мягких и жёстких решений линейных двоичных блоковых кодов, ясно указывает на важное значение параметра минимальное кодовое расстояние для качества кода. Если мы, например, рассмотрим декодирование мягких решений, верхняя граница вероятности ошибки, представленная в (8.1.52), указывает на то, что для заданной скорости кода  вероятность ошибки в канале с АБГШ уменьшается экспоненциально с . Если эту границу использовать в соединении с нижней границей для , данную ниже, мы получаем верхнюю границу для , которую можно достичь многими известными кодами. Аналогично, мы можем использовать верхнюю границу данную в (8.1.82) для вероятности ошибки при декодировании жёстких решений в соединении с нижней границей для  для получения верхней границы для вероятности ошибочного декодирования линейных двоичных блоковых кодов в ДСК.

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

Простая верхняя граница для минимального расстояния двоичного или недвоичного линейного блокового кода  была дана в (8.1.14) как . Удобно нормировать это выражение через длину блока . Это даёт

,                      (8.1.106)

где  - скорость кода. Для больших  слагаемым  можно пренебречь. Если код имеет наибольшее возможное расстояние, т.е. , его называют разделимым кодом с максимальным расстоянием. Исключая случаи тривиального кода  для передачи двоичных сообщений с повторением, не существует двоичных разделимых кодов с максимальным расстоянием. Фактически верхняя граница в (8.1.106) для двоичных кодов весьма неточная. С другой стороны, существуют недвоичные коды с . Например, коды Рида-Соломона, которые представляют подкласс БЧХ кодов, являются разделимыми кодами с максимальным расстоянием. В дополнение к верхней границе, данной выше, имеется несколько плотных границ для минимального расстояния линейных блоковых кодов. Мы вкратце опишем четыре важные границы, три из них верхние границы, а четвертая нижняя. Доказательство этих границ сложное и не представляет особого интереса в нашем последующем обсуждении. Интересующемуся читателю можно порекомендовать главу 4 книги Питерсона и Уэлдона (1972) с этими доказательствами.

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

.                    (8.1.107)

Поскольку эффективность кода, измеряемая параметром , связана с минимальным расстоянием, (8.1.107) является верхней границей для минимального расстояния. Ее называют верхней границей Хемминга.

Получена асимптотическая форма (8.1.107) при . Теперь для любого  пусть  является наибольшим целым , при котором выполняется (8.1.107). Тогда можно показать (Питерсон и Уэлдон, 1972) что при  отношение  для каждого  блокового кода не может превысить , где  удовлетворяет условию

,                    (8.1.108)

а  - двоичная энтропийная функция, определяемая (3.2.10).

Обобщение границы Хемминга на недвоичные коды с основанием  простое:

                    (8.1.109)

Другую верхнюю границу, открытую Плоткиным (1960), можно определить так. Число проверочных символов, требуемое для достижения минимального расстояния  в линейном блоковом коде , удовлетворяет неравенству

.                    (8.1.110)

Для двоичного кода (8.1.110) можно выразить так

.

В пределе, когда , при  (8.1.110) приводит к

.                     (8.1.111)

Наконец, имеется другая плотная верхняя граница для минимального расстояния, полученная Элиасом (Берлекэмп, 1968). Её можно выразить в асимптотической форме:

,                    (8.1.112)

где параметр  связан со скоростью кода уравнением

.                      (8.1.113)

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

,                       (8.1.114)

где  связано со скоростью кода уравнением

.                       (8.1.115)

Эта нижняя граница - частный случай нижней границы, открытой Гильбертом (1952) и Варшамовым (1957), которая применима для недвоичных и двоичных блоковых кодов.

Асимптотические границы, данные выше, приведены на рис. 8.1.16 для двоичных кодов. С целью сравнения на рисунке даны также кривые минимального расстояния, как функции скорости кода для БЧХ кодов с длиной блоков  и 63.

Видно, что для  и 63 нормированное минимальное расстояние хорошо ложится над нижней границей Варшамова-Гильберта. По мере увеличения длины блока , эффективность БЧХ кодов ослабевает. Например, когда , кривая нормированного минимального расстояния ложится близко к границе Варшамова—Гильберта. Если  возрастает выше , нормированное минимальное расстояние БЧХ кода продолжает уменьшается и падает ниже границы Варшамова-Гильберта. Это значит, что  приближается к нулю по мере того как  стремится к бесконечности. Следовательно, БЧХ коды, которые являются наиболее важным классом циклических кодов, не очень эффективны при больших длинах блоков.

Рис. 8.1.16. Верхняя и нижняя границы нормированного минимального расстояния в функции от скорости кода