Скляр Б. Цифровая связь (2003) (1151859), страница 82
Текст из файла (страница 82)
И наконец, для синдрома Яз индекс 7'и 1, ..., л — 1 означает, что каждый синдром состоит из л — 1 = 3 бит. В этой главе индексы часто опускаются, и векторы 1)„ел гз и Бз зачастую обозначаются как )), е, г и Я. Читателю следует помнить, что для этих векторов индексы всегда подразумеваются, даже в тех случаях, когда они опушены для простоты записи. 367 Л а Пмммйыып Лппчмып копы ~ Л пт 6.5. Возможность обнаружения и исправления ошибок 6.5.1.
Весовой коэффициент двоичнык векторов и расстояние между ними Конечно же, понятно, что правильно декодировать можно не все модели ошибки. Возможности кода для исправления ошибок в первую очередь определяются его структурой. Весовой коэф4ициент Хэмминга (Наппшпя ъе!я)гг) в(()) кодового слова Ю определяется как число ненулевых элементов в ().
Для двоичного вектора это эквивалентно числу единиц в векторе. Например, если !3 = 1 00 1 0 1 1 0 1, то в(Щ = 5. Расстояние Хэмминга (Нагпш!пя сйяапсе) между двумя кодовыми словами Н и Ч, обозначаемое как 4(А Ч), определяется как количество элементов, в которых они отличаются. ()=100101!01 Ч=011110100 а'((), Ч) = б Согласно свойствам сложения по модулю 2, можно отметить, что сумма двух двоичных векторов является другим двоичным вектором, двоичные единицы которого расположены на тех позициях, которглми эти векторы отличаются. !)чЧ=111011001 Таким образом, можно видеть, что расстояние Хэмминга между двумя векторами равно весовому коэффициенту Хэмминга их суммы, т.е. г(((), Ч) = и(() + Ч).
Также видно, что весовой коэффициент Хэмминга кодового слова равен его расстоянию Хэмминга до нулевого вектора. 6.5.2. Минимальное расстояние для линейного кода Рассмотрим множество расстояний между всеми парами кодовых слов в пространстве Ч„. Наименьший элемент этого множества называется минимальным расстоянием кода и обозначается ь( . Как вы думаете, почему нас интересует именно минимальное расстояние, а не максимальное? Минимальное расстояние подобно наиболее слабому звену в цепи, оно дает нам меру минимальных возможностей кода и, следовательно, характеризует его мощность, Как обсуждалось ранее, сумма двух произвольных кодовых слов дает другой элемент кодовых слов подпространства. Это свойство линейных кодов формулируется просто: если 1) и Ч вЂ” кодовые слова, то и ЧУ = !) + Ч тоже должно быть кодовым словом.
Следовательно, расстояние между двумя кодовыми словами равно весовому коэффициенту третьего кодового слова, т.е. а(!), Ч) = и(()+ Ч) = в (Чу). Таким образом, минимальное расстояние линейного кода можно определить, не прибегая к изучению расстояний между всеми комбинациями пар кодовых слов. Нам нужно лишь определить вес каждого кодового слова (за исключением нулевого вектора) в подпространстве; минимальный вес соответствует минимальному расстоянию ь( „. Иными словами, а', соответствует наименьшему из множества расстояний межлу нулевым кодовым словом и всеми остальными кодовыми словами. Збб Гпа ай ка а н 1 6.5.3. Обнаружение и исправление ошибок Задача декодера после приема вектора г заключается в оценке переданного кодового слова Еп Оптимальная стратегия декодирования может быть выражена в терминах алгоритма максимального аравданадабия (см.
приложение Б); считается, что передано было слово Ц, если р(г~(),) = пмх р(г!(//). па вссм и, (6.41) Поскольку для двоичного симметричного канала (Ь|пагу зугпгпе(пс сЛаппе! — ВЯС) правдоподобие Ц относительно г обратно пропорционально расстоянию между г и Ем можно сказать, что передано было слово Ем если с/(г(1),) = пап с/(г((/ ) . па всем ц (6.42) Другими словами, декодер определяет расстояние между г и всеми возможными пере- данными кодовыми словами Ц, после чего выбирает наиболее правдоподобное Еп для которого с/(г 1/ ) й с/(г (/з ) лля / / 1 ьг и 1 Ф / (6.43) Е б йопсмомсноеть огснпомспмммп и иоппявленмя ошибок Збе где М = 2' — это размер множества кодовых слов.
Если минимум не олин, выбор между минимальными расстояниями является произвольным. Наше обсуждение метрики расстояний будет продолжено в главе 7. На рис. 6.!3 расстояние между двумя кодовыми словами () и Ч показано как расстояние Кэмминга. Каждая черная точка обозначает искаженное кодовое слово. На рис. 6.!3, а проиллюстрирован прием вектора г„находящегося на расстоянии 1 от кодового слова () и на расстоянии 4 от кодового слова Ч. Декодер с коррекцией ошибок, следуя стратегии максимального правдоподобия, выберет при принятом векторе г, кодовое слово ().
Если г, получился в результате появления одного ошибочного бита в переданном векторе кода (/, декодер успешно исправит ошибку. Но если же это произошло в результате 4-битовой ошибки в векторе кода Ч, декодирование будет ошибочным. Точно так же, как показано на рис. 6.13, б, двойная ошибка при передаче (/ может привести к тому, что в качестве принятого вектора будет ошибочно определен вектор г„находящийся на расстоянии 2 от вектора 1/ и на расстоянии 3 от вектора кода Ч. На рис. 6.13, в показана ситуация, когда в качестве принятого вектора ошибочно определен вектор г„который является результатом тройной ошибки при передаче и находится на расстоянии 3 от вектора кода ь/ и на расстоянии 2 от вектора Ч. Из рис.
6.13 видно, что если задача состоит только в обнаружении ошибок, а не в их исправлении, то можно определить искаженный вектор — изображенный черной точкой и представляющий одно-, двух-, трех- и четырехбитовую ошибку. В то же время пять ошибок при передаче могут привести к приему кодового слова Ч, когда в действительности было передано кодовое слово 1); такую ошибку невозможно будет обнаружить. Из рис.
6.13 можно видеть, что способность кода к обнаружению и исправлению ошибок связана с минимальным расстоянием между кодовыми словами. Линия решения на рисунке служит той же цели, что и в процессе демодуляции, — для разграничения областей решения. Линия решений Область 1 ! Область а ц гз б! гз е) Рнс. 6.13 лозметкности олрвделезтя и исправления отнбскз а) принятый вектор г,; б) принятый вектор гт,.
в) ирнюииый вектор гз В примере, приведенном на рис. б,13, критерий принятия решения может быть следующим: выбрать Ю, если г попадает в область 1, и выбрать и', если г попадает в область 2. Выше показывалось, что такой код (при т(, =5) может исправить две ошибки. Вообще, сиособноаиь кода к исправлению ошибок г определяется, как максимальное число гарантированно исправимых ошибок на кодовое слово, и записывается следующим образом (4]: (бА4) Здесь Ы означает наибольшее целое, не превышающее х. Часто код, который исправляет все искаженные символы, содержащие ошибку в г или меньшем числе бит, также может исправлять символы, содержащие г+ 1 ошибочных бит.
Это можно увидеть на рис. б.11. В этом случае и', =3, поэтому из уравнения (6.44) можно видеть, что исправимы все модели ошибки из г = 1 бит. Также поправима одиночнпя модель ошибки, содержащая г+ 1 (т.е. 2) ошибочных бит. Вообще, линейный код (л, к), способный исправлять все символы, содержащие г ошибочных бит, может исправить всего 2" ~ моделей ошибок. Если блочный код с возможностью исправления символов, имеющих ошибки в с бит, применяется для исправления ошибок в двоичном симметричном канале с вероятностью перехода р, то вероятность ошибки сообщения Рм (вероятность того, что декодер совершит неправильное декодирование и л-битовый блок содержит ошибку) можно оценить сверху, используя уравнение (б.18): (б.45) 370 Гилля я Кинлпннпа нппиппллнип. ни тн 1 Оценка переходит в равенство, если декодер исправляет все модели ошибок, содержащие до ! ошибочных бит включительно, но не модели с числом ошибочных бит, большим !.
Такие декодеры называются декодерами с еграниченчми расстоянием. Вероятность ошибки в декодированном бите Ра зависит от конкретного кода и декодера. Приближенно ее можно выразить следующим образом [5]: (6.46) В блочном коде, прежде чем исправлять ошибки, необходимо их обнаружить. (Или же код может использоваться только для определения наличия ошибок.) Из рис.
6.13 видно, что любой полученный вектор, который изображается черной точкой (искаженное кодовое слово), можно определить как ошибку. Следовательно, возможность определения наличия ошибки дастся следующим выражением; е =г(, — 1. (6.47) 6.6.3.1. Распределение весовых коэффициентов кодовых слов Пусть А, — количество кодовых слов с весовым коэффициентом у в линейном коде (и, А). Числа А,, Аь ..., А„называются распределением весовых коэффициентов этого кода. Если код применяется только для обнаружения ошибок в двоичном симметричном канале, то вероятность того, что декодер не сможет определить ошибку, можно рассчитать, исходя из распределения весовых коэффициентов кода (5]: Р,,а",> А,р (1-р)"- г=! (6.48) тле р — вероятность перехода в двоичном симметричном канале.
Если минимальное расстояние кода равно г(„, значения от А, до Аг ! равны нулю. Згт П Ч япаипииппп пииап пааииа и ипппааааииа и и Блочный код с минимальным расстоянием И, гарантирует обнаружение всех моделй ошибок, содержащих !г'„— 1 или меньшее число ошибочных бит. Такой код также способен обнаружить и более длинную часть модели ошибки, содержащую На, или более ошибок Фактически код (л, гг) может обнаружить 2" — 2' моделей ошибок длины в. Объясняется это следующим образом. Всего в пространстве 2" и-кортежей существует 2" — 1 возможных ненулевых моделей ошибок. Даже правильное кодовое слово — это потенциальная модель ошибки. Поэтому всего существует 2"-1 моделей ошибки, которые идентичны 2'-1 ненулевым кодовым словам.
При появлении любая из этих 2' — 1 моделей ошибки изменяет передаваемое кодовое слово Ц на другое кодовое слово Ог Таким образом, принимается кодовое слово Оп и его синдром равен нулю. Декодер принимает О! за переданное кодовое слово, и поэтому декодирование дает неверный результат. Следовательно, существует 2' — 1 необнаружимых моделей ошибки. Если модель ошибки не совпадает с одним из 2' кодовых слов, проверка вектора г с помощью синдромов дает ненулевой синдром и ошибка успешно обнаруживается. Отсюда следует, что существует ровно 2' — 2' выявляемых моделей ошибки. При больших л, когда 2" « 2", необнаружимой будет только незначительная часть моделей ошибки.
Пример 6.5. Вероятность необнаруженной ошибки в коде Пусть код (6, 3), введенный в разделе 6.4.3, используется только дяя обнаружения наличия ошибок. Рассчитайте вероятность необнару:венной ошибки, если применяется двоичный симметричный канал, а вероятность перехода равна 10 ". Решение Распределение весовых коэффициентов этого кода выглядит следующим образом: Ао = 1, А~ = Аз =О, Аз= 4, А5 = О, Аб —- О.
Следовательно, используя уравнение (6.48), можно записать следующее: Рм=4Р (1-Р) + ЗР (1-Р) . Для р = 10 " вероятность необнаруженной ошибки будет равна 3„9 х 10~. 6.5.3.2. Одновременное обнаружение и исправление ошибок Возможность исправления ошибок следует из гарантированного максимума О), где г определяется уравнением (6.44), для одновременного обнаружения класса ошибок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
