8.1.5. Декодирование жёстких решений

Границы, данные в разделе 8.1.4 для качества кодированных сигналов в канале с АБГШ, основывались на предпосылке, что отсчёты на выходе согласованного фильтра или коррелятора не квантованы. Хотя такая обработка обеспечивает наилучшее качество, принципиальным ограничением являются вычислительные затраты по формированию корреляционных метрик и их сравнению для определения наибольшей. Количество вычислений получается чрезмерным, когда число кодовых слов велико.

Для сокращения вычислительных затрат аналоговые отсчеты на выходе согласованных фильтров можно квантовать и операции декодирования выполнить как цифровые. В этом подразделе мы рассмотрим крайний случай, когда каждый отсчет, соответствующий одному символу кодового слова, квантуется на два уровня: нуль и единица. Это значит, что принято решение (жёсткое решение) о том, передан ли с каждым кодовым символом кодового слова «0» или «1». Результирующий канал с дискретным временем (состоящий из модулятора, канала с АБГШ и демодулятора) образует ДСК с вероятностью ошибки . Если для передачи кодового символа кодового слова используется двоичная ФМ и осуществляется когерентный приём, то

. (8.1.73)

С другой стороны, если для передачи кодового символа кодового слова используется двоичная ЧМ, тогда

- при когерентном детектировании (8.1.74)

- при некогерентном детектировании. (8.1.75)

Декодирование по минимальному расстоянию (правило максимального правдоподобия). Жёсткие решения демодулятора для каждого принятого кодового слова поступают на декодер, который сравнивает принятое кодовое слово с возможными переданными кодовыми словами и принимает решение в пользу кодового слова, которое ближе всего по Хеммингу к принятому кодовому слову, т.е. отличается от него в наименьшем числе разрядов. Это правило декодирования по минимальному расстоянию оптимально в том смысле, что оно обеспечивает минимальную вероятность ошибочного декодирования кодового слова в двоичном симметричном канале.

Концептуально простой, но в вычислительном отношении неэффективный, метод для декодирования жёстких решений сводится к тому, чтобы сначала суммировать принятый вектор кодового слова со всеми возможными к передаче кодовыми словами , чтобы получить векторы ошибок . Таким образом, представляет ошибочное событие, которое должно произойти в канале для того, чтобы превратить кодовое слово в данное принятое кодовое слово. Число ошибок при превращении в принятое кодовое слово как раз равно числу единиц в . Таким образом, если мы просто сосчитаем вес каждого их векторов и примем решение в пользу кодового слова, которое привело к наименьшему весу вектора ошибки, мы фактически имеем реализацию правила декодирования по минимуму расстояния.

Более эффективный метод для декодирования жёстких решений сводится к испольвованию проверочной матрицы . Для детальной разработки вопроса, предположим, что - это переданное кодовое слово, a - принятое кодовое слово на выходе демодулятора. В общем случае можно выразить так

где означает произвольный вектор ошибок. Произведение даёт с учётом (8.1.9)

, (8.1.76)

где - мерный вектор называется синдромом образца ошибки. Другими словами, вектор имеет нулевые компоненты для тех уравнений проверочных символов, которые выполняются, и ненулевые компоненты для тех уравнений проверочных символов, которые не выполняются. Таким образом, содержит образец неудач проверок.

Подчеркнём, что синдром является характеристикой образцов ошибок, но не переданных кодовых слов. Далее заметим, что имеется возможных образцов ошибок, но только синдромных. Следовательно, различные образцы ошибок приводят к одинаковым синдромам.

Предположим, мы сконструируем таблицу декодирования , в заголовке которой запишем все возможных кодовых слов, начиная кодовым словом из одних нулей в первом (самом левом) столбце. Это кодовое слово из одних нулей представляет также образец ошибки, состоящий из одних нулей. Мы заполним первый столбец путём записи сначала всех образцов ошибок с весом 1 (их число равно ). Если , мы можем затем записать образцы двойных ошибок, затем образцы тройных ошибок и т.д., пока не получим общее записей в первом столбце. Таким образом, число строк, которые можно иметь в таблице, равно , что равно числу возможных синдромов. Далее мы суммируем каждый образец ошибки из первого столбца с соответствующими кодовыми словами, расположенными в верхней строке таблицы. Так мы заполняем остаток таблицы следующим образом

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

Пример 8.1.10. Сконструируем стандартное расположение для систематического кода (5, 2) с порождающей матрицей

Этот код имеет минимальное расстояние . Стандартное расположение дано в табл. (8.1.7). Заметим, что в этом коде среди 8 лидеров смежных классов один состоит из одних нулей, пять лидеров имеют вес, равный 1 и два имеют вес, равный 2. Хотя имеется много больше образцов двойных ошибок, здесь достаточно двух, чтобы заполнить таблицу.

Табл. 8.1.7. Стандартное расположение для кода (5, 2)

Кодовые слова
00000	01011	10101	11110
00001	01010	10100	11111
00010	01001	10111	11100
00100	0 1111	10001	11010
01000	00011	11101	10110
10000	11011	00101	01110
11000	10011	01101	00110
10010	11001	00111	01100

Они были выбраны так, чтобы соответствующие им синдромы отличались от тех, которые соответствуют одиночным ошибкам.

Теперь предположим, что являются лидером смешанного класса, и что было передано кодовое слово . Тогда образец ошибки , приводит к принимаемому кодовому слову

Синдром равен

Ясно, что все принимаемые кодовые слова в тех же смежных классах, образованные из тех же , имеют одинаковые синдромы, поскольку последние зависит только от образцов ошибки. Далее, каждый смежный класс, образованный различным имеет свой синдром. Установив эти характеристики из стандартного расположения, мы можем просто сконструировать синдромную таблицу декодирования, в которой запишем синдромов и соответствующие лидеров смешанных классов, которые представляют образцы ошибок с минимальным весом. Затем, для данного принимаемого кодового вектора мы вычисляем синдром

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

Пример 8.1.11. Рассмотрим код (5, 2) со стандартным расположением, данным в таблице (8.1.7). Синдромы, соответствующие наиболее правдоподобным образцам ошибок, даны в таблице (8.1.8). Теперь предположим, что действительный вектор ошибок в канале

Синдром, вычисленный для этой ошибки, равен . Ошибка, определяемая по этому синдрому из таблицы, равна . Когда суммируется с , результат приведёт к ошибке декодирования. Другими словами, код (5,2) корректирует все одиночные ошибки и только две двойные ошибки, именно и .

Табл. 8.1.8. Таблица синдромов для кода (5, 2)

Синдром

Вектор ошибки

000

001

010

100

011

101

110

111

00000

00001

00010

00100

01000

10000

11000

10010

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

Для более подробного обсуждения рассмотрим систематический циклический код и представим принимаемый кодовый вектор полиномом . Вобщем , где -переданное кодовое слово, а - вектор ошибки. Таким образом, имеем

. (8.1.77)

Теперь разделим на порождающий полином . Это деление даёт

или, что эквивалентно,

. (8.1.78)

Остаток — полином степени, меньшей или равной . Если объединить (8.1.77) и (8.1.78), получим

. (8.1.79)

Это соотношение показывает, что остаток , полученный отделения на , зависит только от полинома ошибки и, следовательно, - это просто синдром , связанный с образцом ошибки . Таким образом,

, (8.1.80)

где - полином синдрома степени меньшей или равной . Если делится на точно (без остатка), тогда и принятое слово определяет решение декодера: .

Деление на порождающий поливом можно выполнить посредством регистра сдвига, выполняющего деление, как описано ранее. Сначала принимаемый вектор передвигается по -каскадному регистру сдвига, как показано на рис. 8.1.9. Первоначально все ячейки регистра сдвига обнулены, а ключ находится в положении 1. После того как весь принятый -символьный вектор вошёл в регистр, содержимое ячеек образует синдром в порядке следования символов, указанном на рис. 8.1.9. Эти символы поочерёдно извлекаются из регистра при установке ключа в положение 2. По заданному синдрому от -каскадного регистра сдвига и справочной таблице можно идентифицировать наиболее вероятный вектор ошибки.

Рис. 8.1.9. -каскадный регистр сдвига для вычисления синдрома

Пример 8.1.12. Рассмотрим вычисление синдрома для циклического кода Хемминга (7,4) с порождающим полиномом . Предположим, что принят вектор . Он подаётся на трехкаскадный регистр, показанный на рисунке 8.1.10.

Рис. 8.1.10. Вычисление синдрома для циклического кода (7,4) с порождающим полиномом при принимаемом векторе

После семи сдвигов содержимое регистров сдвига 110, что соответствуют синдрому . Этому синдрому соответствует наиболее правдоподобный вектор ошибки и, следовательно,

Информационные символы 1000.

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

Для класса циклических кодов и более сложного класса БЧХ кодов были разработаны более эффективные алгоритмы декодирования жёстких решений. Описание этих алгоритмов требует дальнейшей разработки вычислительных методов в конечных полях, которые находятся вне нашей области охвата теории кодирования. Достаточно указать, что существует алгоритмы эффективного декодирования, что делает возможным реализовать длинные БЧХ коды с большой избыточностью в практике цифровых систем связи.

Интересующего читателя отправляем к книгам Питерсона и Уэлдона (1972), Лина и Костелло (1983), Блейхута (1983), Берлекэмпа (1968) и к статье Форни (1965).

Способность обнаружения и исправления ошибок. Из вышеизложенного ясно, что когда синдром содержит одни нули, принимаемое кодовое слово являются одним из возможных к передаче кодовых слов. Поскольку минимальное расстояние между парой кодовых слов равно , образец ошибки весом может трансформировать один из этих кодовых слов кода в другое кодовое слово. Если это случается, мы имеем необнаруженную ошибку. С другой стороны, если действительное число ошибок меньше, чем , синдром будет иметь ненулевой вес. Если это случится, мы обнаружили наличие одной или больше ошибок в канале. Ясно, что блоковый код способен обнаружить ошибок. Обнаружение ошибок можно использовать совместно со схемой автоматического запроса - повторения (АЗП) для повторной передачи кодового слова.

Способность кода исправлять ошибки также зависит от минимального расстояния. Однако, число исправляемых образцов ошибок ограничено числом возможных синдромов или лидеров смежных классов в стандартном расположении. Чтобы определить способность кода исправлять ошибки, удобно рассматривать кодовых слов как точки в -мерном пространстве. Если каждое кодовое слово рассматривать как центр сферы с радиусом (расстоянием Хемминга) , то наибольшее значение, которое может принять без пересечения (или касания) с любой парой из сфер, равно , где означает наибольшее целое, содержащееся в . Внутри каждой сферы лежат всевозможные принимаемые кодовые слова с расстоянием меньшим или равным от действительно переданного кодового слова. Следовательно, любой принимаемый кодовый вектор, который попадает внутрь сферы, декодируется в разрешённое кодовое слово в центре сферы. Это подразумевает, что код с минимальным расстоянием пособен исправить ошибок. Рис. 8.1.11 является двумерной моделью кодовых слов и сфер.

Как описано выше, код может быть использован для обнаружения ошибок или для исправления ошибок. Ясно, что для исправления ошибок подразумевается, что мы обнаружили ошибок. Однако, возможно также обнаружить больше чем ошибок, если мы пойдём на компромисс по исправляющей способности кода. Например, код с может исправить ошибки. Если мы желаем обнаружить четыре ошибки, мы можем это сделать, уменьшив радиус сферы вокруг каждого кодового слова с 3 до 2. Таким образом, обнаруживаются образцы с четырьмя ошибками, но только образцы с двумя ошибками исправляются. Другими словами, если возникнут только две ошибки, они исправятся, а если возникнут три или четыре ошибки, приёмник может запросить повторение. Если возникают более чем четыре ошибки, они останутся необнаруженными, если кодовые слова попадают внутри сферы радиуса 2. Аналогично, при можно обнаружить пять ошибок и одну исправить. В общем, код с минимальным расстоянием может обнаружить ошибок и исправить ошибок, если

и .

Рис. 8.1.11. Представление кодовых слов в виде центров сфер радиуса

Вероятность ошибки при декодировании с исправлением ошибок. Мы завершим этот раздел определением вероятности ошибки при декодировании жёстких решений для линейных двоичных блоковых кодов, основываясь только на исправлении ошибок.

Из вышеизложенного ясно, что оптимальный декодер в симметричном двоичном канале будет декодировать правильно, если (но не обязательно только если) число ошибок в кодовом слове меньше, чем половина минимального расстояния кода. Это значит, число ошибок не выше всегда исправится. В двоичном симметричном канале без памяти ошибки в отдельных символах возникают независимо. Следовательно, вероятность ошибок в блоке из символов равна

, (8.1.81)

и, следовательно, вероятность ошибки кодового слова ограничена сверху выражением

. (8.1.82)

Равенство в (8.1.82) имеет место, если линейный блоковый код совершенный. Чтобы описать базовые характеристики совершенного кода, предположим, что мы размещаем сферу радиусом вокруг каждого возможного кодового слова. Каждая сфера вокруг кодового слова содержит набор всех кодовых слов с расстоянием Хемминга относительно центра, меньшим или равным . Теперь число кодовых слов в сфере радиуса равно .

Поскольку имеется возможных передаваемых кодовых слов, имеется непересекающихся сфер, каждая с радиусом . Общее количество кодовых слов, включённых в сферах, не может превышать возможных на приёме кодовых слов. Таким образом, код, исправляющий ошибок, должен удовлетворять неравенству или, что эквивалентно,

. (8.1.83)

Совершенный код имеет свойство, что все сферы с радиусом вокруг возможных к передаче кодовых слов разъединены и каждое принимаемое кодовое слово попадает в одну из сфер. Таким образом, каждое принимаемое кодовое слово самое большее находится на расстоянии от возможных к передаче кодовых слов, и в (8.1.82) выполняется знак равенства. Для такого кода все образцы ошибки с весом, меньшим или равным , исправляются оптимальным декодером. С другой стороны, образцы ошибки весом или большим не могут быть исправлены. Следовательно, выражение для вероятности ошибки, даваемое (8.1.82), выполняется со знаком равенства. Код Голея (23,12), имеющий и , является совершенным кодом. Коды Хемминга, которые имеют три параметра , и , также совершенные коды. Эти – два нетривиальных кода и тривиальный код, состоящий из двух кодовых слов с нечётным числом символов единиц и нулей, причём , являются единственными совершенными двоичными блоковыми кодами. Эти коды оптимальны в ДСК в там смысле, что они приводят к меньшей вероятности ошибки декодирования среди всех кодов, имеющих ту же длину блока и то же число информационных символов.

Оптимальные свойства, определённые выше, имеют место и для квазисовершенных кодов. Квазисовершенный код характеризуется свойством, что все сферы с радиусом Хемминга вокруг возможных к передаче кодовых слов не пересекаются, и каждое принимаемое кодовое слово находится самое большее на расстоянии от возможных к передаче кодовых слов. Для такого кода все образцы ошибок с весом, меньшим или равным и некоторые образцы ошибок весом исправляются, но ни один образец ошибки весом или больше не исправляются в кодовом слове. Ясно, (8.1.82) является для этих кодов верхней границей для вероятности ошибки, а

(8 184)

является нижней границей.

Более точную меру качества для квазисовершенных кодов можно получить, используя неравенство в (8.1.83). Общее число кодовых слов, исключая сфер радиусом , равно

Если эти кодовые слова поровну разделить на наборов и каждый набор связать с одной из сфер, тогда число кодовых слов в каждой сфере увеличивается на

(8.1.85)

кодовых слов, имеющих расстояние от переданных кодовых слов. Как следствие, от образцов ошибок с расстоянием от каждого кодового слова мы можем исправить образцов ошибок. Таким образом, вероятность ошибочного декодирования квазисбвершенного кода можно выразить так:

. (8.1.86)

Имеется много известных квазисовершенных кодов, хотя они не существуют для всех наборов и . Поскольку такие коды оптимальны для двоичного симметричного канала, то любой линейный блоковый код должен иметь вероятность ошибки, которая, по крайней мере, принимает значение (8.1.86). Следовательно, (8.1.86) является нижней границей вероятности ошибки декодирования для любого линейного блокового кода , где - наибольшее целое, так чтобы .

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

. (8.1.87)

С другой стороны, не может быть больше, чем умноженная в раз вероятность ошибочного декодирования переданного кодового слова в ближайшее кодовое слово, которое имеет расстояние от переданного кодового слова:

. (8.1.88)

Когда велико, нижняя граница (8.1.88) и верхняя граница (8.1.87) весьма далеки одна от другой. Плотную верхнюю границу для можно получить, используя границу Чернова, представленную раньше в разделе 2.1.6. Предположим снова, что передается кодовое слово из одних нулей. При сравнении принимаемого кодового слова с кодовым словом из одних нулей и с кодовым словом веса вероятность ошибки декодирования, полученная из границы Чернова (задача 8.22), ограничена сверху выражением

. (8.1.89)

Объединение вероятностей двоичных решений ведет к верхней границе

. (8.1.90)

Более простую версию (8.1.90) можно получить, если взять вместо распределения весов. Т.е.

. (8.1.91)

Конечно, (8.1.90) - более плотная граница, чем (8.1.91).

В разделе (8.1.6) мы сравним различные границы, данные выше, для конкретного кода, а именно кода Толея (23, 12). Дополнительно мы сравним характеристики качества при декодировании жёстких и мягких решений.