Главная > Помехоустойчивое кодирование > Коды, исправляющие ошибки
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

1.3. Блоковые коды

Все коды, описываемые в этой книге, за исключением кодов, рассматриваемых в гл. 12, являются блоковыми кодами. Именно для блоковых кодов Шеннон доказал свою фундаментальную теорему о дискретных каналах с шумом [119], в которой утверждается, что" канал имеет точно определяемую пропускную способность и что при помощи подходящих кодов можно передавать информацию с любой скоростью, не превосходящей пропускной способности канала, так, чтобы вероятность ошибки после декодирования была произвольно малой. Блоковые коды применяются не только в теории связи, но также покрайней мере еще в двух других областях. Они являются основой для распределения нагрузок при помощи переключательных матриц [40, 49, 78, 114], которые не только более эффективны, чем обычные системы адресов ячеек памяти, но и позволяют автоматически исправлять отдельные ошибки, произошедшие из-за неполадок устройства. Они аналогичны по математической структуре некоторым планам статистических экспериментов [5, 48].

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

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

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

Пример. Предположим, что имеются четыре возможных сообщения a, b, с и d и что сообщение будет передаваться с помощью двоичного блокового кода длины 5. Тогда должны быть выбраны четыре кодовых слова, например 11000 для а, 00110 для для для

Кроме того, должны быть записаны решения, принимаемые на приемном конце для каждого из слов, или последовательностей пяти символов, которые могут быть получены в результате передачи. Пример того, как это может быть сделано, приведен на рис. 1.3.

Рис. 1.3. Таблица декодирования для двоичного кода.

Код и схема декодирования, показанные на рис. 1.3, позволяют выполнять правильное декодирование, если в полученном векторе имеется не более чем одна ошибка, т. е. не более чем один искаженный символ. Действительно, все пять слов, которые получаются в результате ошибки в одном символе, расположены под соответствующим кодовым словом. Правильно декодируются и некоторые другие комбинации ошибок, хотя остальные комбинации могут декодироваться и неправильно. Например, если передавалось слово и произошли две ошибки, в результате чего получилось слово то декодирование будет произведено правильно, так как слово 11110 находится в столбце под Если же в результате двух ошибок получилось слово 110 11, то оно будет неправильно декодировано в слово поскольку 110 11 в табл. 1.3 находится в столбце под 10 0 11.

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

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

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

Рис. 1.4. Двоичный симметричный канал.

Рис. 1.5. Двоичный стирающий канал.

Заметим, что в терминах общей схемы, изображенной на рис. 1-2, этот "канал" включает а себя устройствокодирующее двоичные символы в сигналы на входе канала, собственно канал и устройство, декодирующее сигналы на выходе канала в двоичные символы.

Другим интенсивно изучавшимся идеализированным каналом является двоичный стирающий канал, изображенный на рис. -Для этого канала задается вероятность того, что будет получен тот же символ, который передавался, и вероятность того, что передаваемый символ будет стерт. (Стертый символ обозначается через Воздействия канала на различные символы предполагаются независимыми. Заметим, что на выходе этого канала известны положения искаженных символов, и этот факт делает обычно исправление стираний более легким, чем исправление ошибок. Обобщения стирающего канала включают недвоичный стирающий канал и канал со стираниями и ошибками. Стирающий канал является идеализацией системы, изображенной на рис. 1.2, в которой устройство, декодирующее сигналы на выходе канала в двоичные символы, выдает в сомнительных случаях символ, соответствующий стиранию и отличный от 0 и от 1.

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

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

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

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

Если этот код используется исключительно для обнаружения ошибок, то вероятность правильного приема равна Вероятность необнаружения ошибки, если передавалось слово равна вероятности того, что получено некоторое другое кодовое слово. Поскольку одно кодовое слово отличается от в четырех разрядах, а остальные кодовые слова - в трех разрядах каждое, то

<< Предыдущий параграф Следующий параграф >>
Оглавление