У. Питерсон - Коды, исправляющие ошибки (1267328), страница 4
Текст из файла (страница 4)
На основе информации, содержащейся в полученном наборе длияы п, на приемном конце принимается решение относительно переданного кодового слова. Это решение является статистическим, т. е. по своей природе оно является наилучшей гипотезой, принятой на основе имеющейся информации, и поэтому оно не безошибочно.
При использовании хорошего кода вероятность неверного решения обычно значительно меньше вероятности того, что первоначально поданные на вход канала символы безошибочно воспроизводятся на его выходе. Процесс выбора решения может быть описан математически при помощи таблицы декодирования. Кодовые слова образуют первую строку этой таблицы. Если получено некоторое кодовое слово, естественно предположить, что было передано именно это слово. Решения, принимаемые на приемном конце для других возможных слов на выходе, задаются перечнем под каждым кодовым словом тех возможных слов на выходе, которые могут декодироваться в это кодовое слово.
Таким образом, каждое возможное слово на выходе появляется в таблице декодирования один и только один раз. Пример. Предположим, что четыре возможных сообщения а, Ь, с и г! будут передаваться с помощью двоичного блокового кода длины 5.
Тогда должны быть выбраны четыре кодовых слова, например ! 1 О О О для а, О О 1 ! О для Ь, ! О О ! ! для с и 0 1 1 0 1 для г!. Кроме того, должны быть записаны решения, принимаемые на приемном конце для каждого из 2з = 32 слов или наборов пяти символов, которые могут быть получены. Пример того, как это может быть сделано, приведен на фиг. !.3. Код и схема декодирования, показанные на фиг. 1.3, позволяют выполнять декодирование правильно, если в полученном слове имеется не более чем одна ошибка, т. е.
не более чем один искаженный символ. действительно, все пять слов, которые получаются лютея в результате ошибки в одном символе, расположены под ~~~~~~тствующим кодовым словом. Правильно декоднруются и Кодовые слова 11000 00110 10011 01101 01100 01111 01001 00101 11101 Другие слова принимаемые 1100! 00111 10010 11010 00100 10001 11100 00010 10111 10000 01110 1!011 01000 10110 00011 11110 00000 01011 01010 10100 11111 10101 0000! Фиг. 1.3. Таблица декодирования для двоичного кода с д = я = 2 и п 5. ') Здесь Р = ! — 0 — вероятность получения противоположного символа.— Прим. Ред, некоторые другие комбинации ошибок, но есть комбинации ошибок, которые могут декодироваться неправильно.
Например, если передавалось слово 1 1 0 0 0 и произошли две ошибки, в результате чего получилось слово 1 1 1 1 О, то декодирование будет произведено правильно, так как слово 111! 0 находится в столбце под 11000. Если же в результате двух ошибок получилось слово 1 1011, то оно будет неправильно декодировано в слово 10011, поскольку 11011 на фиг. 1.3 находится в столбце под словом 1 00!!.
В некоторых ситуациях при декодировании может допускаться как одна из возможных альтернатив утверждение, что обнаружена ошибка без каких-либо дополнительных гипотез относительно переданного слова. Осуществить такое декодирование можно, вводя систему обнаружения ошибок, в которой декодер просто сигнализирует об ошибке и не делается никаких попыток принять какие- либо решения, если на выходе получено слово, не совпадающее с кодовым словом. С другой стороны, как упоминалось раньше, в системе может сочетаться исправление и обнаружение ошибок.
Например, для кода, изображенного на фиг. 1.3, полученное слово, лежащее выше пунктирной линии, может декодироваться в кодовое слово, стоящее в начале соответствующего столбца, но в то же время для слов на выходе, лежащих ниже этой пунктирной линии, декодер может просто сигнализировать об кобнаружении ошибки», Это соответствует исправлению одиночных ошибок вместе с обнаружением некоторых комбинаций из двух или более ошибок. Для того чтобы оценить возможности некоторого кода, нужно иметь более точные сведения о канале. Интенсивно исследовался двоичный симметричный канал (ДСК), хотя большинство реальных каналов связи ие слишком точно описывается этой моделью. Этот канал схематически изображен на фнг.
1.4. Для двоичного симметричного канала задается вероятность ь) того, что полученный символ совпадает с передантгым. Предполагается, что Я Р ') н каждый символ не зависит от всех других. (Такие каналы называются каналами без памяти.) Заметим, что этот канал включает в себя модулятор, собственно канал н демодулятор (см.
общую схему на фиг. 1.2). Другим интенсивно изучающимся идеализированным каналом является двоичный стирающий канал, изображенный на фиг. 1.5. для этого канала задаются вероятность Я того, что будет получен тот же символ, который передавался, и вероятность Р = 1 — Я того, что передаваемый символ будет стерт. (Стертый символ обозначается через Х.) Воздействия канала на различные символы предполагаются независимыми. Заметим, что на выходе этого канала известны положения искаженных символов; прн этом обычно исправление стираний оказывается более легким, чем исправление ошибок. Обобщения стирающего канала включают недвоичный стирающий канал и канал са стираниями и ошибками. Стирающий канал является идеализапией системы, изображенной на фиг. 1.2, в которой демодулятор выдает в сомнительных случаях символ, соответствующий стиранию и отличный от О н 1.
Если предположить, что рассматривается симметричный двоичный канал, по которому передается некоторое кодовое слово, то вероятность того, что пе произойдет нн одной ошибки, равна Ц, Вероятность того, что будет одна ошибка в заданном разряде, равна РЯ"-'. Вероятность того, что слово на выходе будет отличаться От ПЕрЕдаННОГО СЛОВа В 1 раЗрядаХ, ранив Ртт~а-'. ПОСКОЛЬКУ Д" Р, то получение па выходе блока без ошибок более вероятно, чем получение блока с ошибками.
Получение любого слова с одной ошибкой более веронтно, чем получение любого слова с двумя или большим числом ошибок, и т. д. В таком случае в предположении, что все кодовые слова имеют одинаковую вероятность быть переданными по каналу, наилучшим решением на приемнике будет всегда декодирование в то кодовое слово, которое отличается от полученного слова в наименьшем числе разрядов. Такое декодирование называется декодированием по методу максимального правдоподобия.
Этот метод может быть обобщен на случай недвоичного канала без памяти. н Предполагая снова, что рассматривается симметричный двои- чый канал, можно следующим образом вычислить вероятность О 0 Ц Фвг. !,4, и ° ° Двоичный симметричный какал. Фиг, 1Л, Даоичиый стирающий канал. правильного двкодирования для кода, изображенного на ГРИГ. ЦП. Допустим, что передавалось слово 1 1 000. Оно будет правильно декодировано, если на выходе получено некоторое слово из соответствующего ему столбца.
Одно нз этих слов не отличается от переданного, пять отличаются в одном разряде и два — в двух разрядах. Поэтому вероятность правильного декодирования Р (правильного декодирования) = 1Р'17+ 5Р'Я4+ 2РзЯз, Аналогичные вычисления могут быть проведены для других кодо. вых слов.
Если этот код используется исключительно для обнаружения ошибок, то вероятность правильного приема равна 1;)А Вероятность необнаружения ошибки, если передавалось слово 11000, равна вероятности того, что при этом получено некоторое другое кодовое слово. Поскольку одно кодовое слово отличается от ! 1 000 в четырех разрядах, а остальные кодовые слова — в трех разрядах каждое, то Р (необнаружения ошибки) = 1Р'(~+ 2Р'Я'. При изучении свойств кодов, исправляющих ошибки, полезно использовать понятие расстояния Хэммннга 11381. Расстояние Хемминга между двумя словами определяется как число разрядов, в которых эти слова отличаются друг от друга.
Таким образом, одна ошибка соответствует расстоянию Хэммннга между переданным и полученным словами, равному 1. Если код используется только для обнаружения ошибок, то для того, чтобы обнаружить все комбинации нз г( — 1 или меньшего числа ошибок, необходимо и достаточно, чтобы минимальное расстояние Хэмминга между кодовыми словами было равно Н.
Действительно, если минимальное расстояние равно г(, то никакая комбинация из г( — 1 ошибок не может перевести одно кодовое слово в другое. Если же минимальное расстояние меньше или равно с1 — 1, то существует некоторая пара слов, отстоящих друг от друга на расстояние, меньшее г(, и поэтому существует комбинация из соответствующего числа ошибок, которая может перевести одно кодовое слово в другое.
Аналогично декодирование, при котором исправляются все комбинации из 1 нли меньшего числа ошибок, возможно тогда и только тогда, когда минимальное расстояние между кодовыми словами равно по меньшей мере 21+ 1. Тогда любое полученное слово с 1' ( 1 ошибками отличается от переданного кодового слова в 1' символах, а от каждого другого кодового слова самое меньшее в 21+ 1 — 1') Е символах. С другой стороны, если минимальное расстояние меньше, чем 21+ 1, то хотя бы в одном случае бкратная ошибка приведет к такому слову на выходе, которое по крайней мере столь же близко к одному из непередававшихся кодовых слов, как и к переданному кодовому слову. Наконец, ана- логичнымн рассуждениями можно доказать, что декодирование, при котором исправляются все комбинации из 1 или меньшего чйсла ошибок и одновременно обнаруживаются все комбинации из 5 нли меньшего числа ошибок (й > 1), возможно тогда и только ~~гда, когда минимальное расстояние между кодовыми словами равно 1+ д+ 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
