Вернер М. Основы кодирования (2004) (1151849), страница 19
Текст из файла (страница 19)
Имеет место необнаруженная ошибка.Сфера декодирования V]Случай I: Распознаваемаяи исправляемая ошибкаСлучай 2: РаспознаваемаяошибкаСлучай 3: НеобнаруженнаяошибкаIV2Г}= V 3•Рис. 2.5. Векторное пространство с кодовыми словами «о»и принятыми словами « X ».Из рисунка ясно, что корректирующая способность кода зависитот расстояния между кодовыми словами. Так как мы имеем дело сдвоичными векторами и расстояние между ними определяется числом несовпадающих компонент, можно записатьп-1(2.20)(=02-4- Свойства линейных блоковых кодовРасстояние, измеренное таким образом, называется расстояниемХэмминга.
Его также можно определить как число отличных отнуля компонент (вес Хэмминга) скалярной суммы векторов v; и Vjd(v ii v i )=w«(v i ®vj).(2.21)Пример: Синдромное декодирование (7,4)-кода Хэмминга.В качестве примера найдем расстояние Хэмминга между кодовыми векторами vi = (1101000) и v 2 = (0110100) из таблицы 2.1.Согласно (2.20) имеемd(vbv2)= (1©0) + (1ф1) + (0©1) + ( 1 ф 1 ) ++(2.22)(0 ф 1) + (0 ф 0) + (0 ф 0) = 3и, с другой стороны, определяя расстояние Хэмминга как (2.21), получаемd(v!,v 2 ) = шнЫ © v 2 ) = w[(1010100)] = 3.(2.23)Важнейшим параметром, определяющим корректирующую способность кода, является минимальное кодовое расстояние d m i n .
Дляего определения мы должны вычислить расстояние Хэмминга между всеми парами слов и найти наименьшее. В случае линейных кодов вычисления можно существенно сократить. Используем для этойцели основное свойство линейных кодов - свойство «замкнутости»векторного кодового пространства. Это свойство следует непосредственно из определения линейных кодов и формулируется следующим образом: любая линейная комбинация кодовых слов является кодовым словом. Рассмотрим множество двоичных кодовых слов{vo, v i , . .
. , v 2 *_i}, образующих код С. Сложим каждое слово этогомножества по модулю два с некоторым зафиксированным произвольным кодовым словом Vj. Тогда множество кодовых слов отобразитсясамо в себя, а вектор v, перейдет в нулевое кодовое слово. Так какпри таком отображении попарные расстояния кодовых слов не изменятся, а вектор Vj выбран произвольно, то d m i n определяется какd m i n = min wtf(v),veC\{0}(2.24)т.е минимальное кодовое расстояние d m i n линейного кода равно ми2нимальному весу ненулевого кодового слова.2Из линейности кода также следует симметричность распределения кодовых расстояний относительно любого кодового вектора Прим.
перев.Глава 2. Линейные блоковые кодыИз таблицы 2.1 следует, что dm\n (7,4)-кода Хэмминга равно 3.Обобщая все приведенные выше рассуждения и примеры, мы можем определить корректирующую способность линейного кода следующим образом.Линейный двоичный (п, к)-код с минимальным расстоянием Хэмминга dmin > 2t + 1 может обнаружить dm\n — 1 ошибок и исправить3t ошибок.2.4-2. Совершенные коды и граница ХэммингаНа рис.
2.5 изображен случай, когда все возможные принимаемыевекторы г принадлежат областям декодирования кодовых слов.Коды, в которых непересекающиеся сферические области декодирования охватывают все векторное пространство размерности пназываются совершенными или плотноупакованными.При использовании совершенных кодов всегда возможна коррекция ошибок (не обязательно правильная). Помимо кодов Хэмминга,в настоящее время известно мало совершенных кодов.Найдем соотношение между параметрами совершенных двоичных (п, к)- кодов, способных исправлять t ошибок.
Будем исходит изтого, что область декодирования совершенного (п,/г)-кода с d m j n =2t+l образуют 2к непересекающихся сфер радиуса t в n-мерном векторном пространстве. Каждая сфера содержит все n-мерные векторы, находящиеся на расстоянии I от соответствующего кодового слова, причем, 0 < I < t. Таким образом, каждой сфере принадлежитровноп- мерных векторов.Так как общий объем непересекающихся сфер не может превышать объем n-мерного векторного пространства, для двоичных кодовимеем(2.26)г=о ^ ' ^? )•(=о3N(2-27)'Если код исправляет все ошибки кратности и < t, то области декодированияпредставляют собой сферы радиуса t в n-мерном пространстве. - Прим.
перев.2.4- Свойства линейных блоковых кодовРавенство имеет место только для совершенных двоичных кодов.Выражение (2.27) называется границей Хэмминга. Граница Хэмминга является нижней оценкой необходимого числа проверочных символов двоичного кода длины п, способного исправлять t ошибок.Из (2.27) следует, что рассмотренный нами (7,4)-код Хэммингаявляется совершенным, так как(2.28)(=02.4-3. Вероятность ошибки декодированияИсходя из предыдущих рассуждений, мы можем определить вероятность необнаружимой ошибки. На самом деле, ошибка не обнаруживается, если посланное кодовое слово в канале переходит в другоекодовое слово.
Из свойства замкнутого векторного пространства относительно операции сложения кода С следует, что в этом случаесама ошибка должна являться кодовым словом. Таким образом, вероятность необнаружимой ошибки определяется суммой вероятностей независимых событий е = v$, где V; 6 С и 1 < г < 2fc. Так какмы рассматриваем ДСК без памяти с вероятностью ошибки Ре, вероятность события, например, е = (0011010), где (0011010) - кодовоеслово из табл. 2.1, равна Р^(1 — Ре)4.
Обозначим через А, число кодовых слов (п, &)-кода С веса г. Тогда вероятность необнаружимойошибки для кода С равнаР — V4APi(\— P\n~i(I 2Q^Для (7,4)-кода Хэмминга значения Ai (распределения весов) можнополучить из таблицы 2.1. Имеем Ло = l,Ai = Ai = 0, A3 = А4 =7, А5 = 0, А§ = 0, Ач = 1.
Если вероятность одного двоичного символа Ре известна, то можно найти вероятность необнаружимой ошибки,используя (2.29).Не зная распределения весов, вероятность необнаружимой ошибки можно оценить сверху какп(2* - l)i^""°.(2.30)Пример: Передача данных с использованием (7,4)-кода Хэмминга.' 146Глава 2. Линейные блоковые кодыДанные кодируются (7,4)-кодом Хэмминга и передаются по каналу с АБГШ. Отношение сигнал/шум в канале равно 6 дБ, чтоэквивалентно вероятности ошибки двоичного символа, равной 0,023.Скорость передачи - 16 кбйт/сек.
Если при декодировании обнаруживается ошибка, то по сигналу переспроса производится повторнаяпередача кодового слова.1. Какова вероятность, что кодовое слово будет приниматься безошибок?2. Какова вероятность необнаружимой ошибки?3. Определите среднюю «эффективную» скорость в битах (т.есреднее число передаваемых информационных бит в секунду).4. Сравните «эффективную» скорость с максимальной теоретически достижимой.Решение.1. Кодовое слово будет передаваться без ошибок, если все 7 двоичных символов будут переданы верно. Для ДСК без памяти с вероятностью ошибки на символ Ре, вероятность безошибочной передачикодового слова равнаРс = (1 - Ре)7.(2.31)Для канала с АБГШ вероятность Ре определяется как функция отSNR и равнаПодставляя Ре в (2.31), получаемРс = (1-0,023)7«0,85..(2.33)2.
Вероятность необнаружимой ошибки получим из (2.29)344375Р г = 7 0 , 0 2 3 0 , 9 7 7 + 7-0,023 -0,977 + 0,023 «7,9-10~ . (2.34)Верхняя оценка Рг (2.30) дает для сравнения(2к - l)P e d m i " w 15 • 0,023 3 « 18 • 10" 5 .(2.35)3. Ввиду пренебрежимо малой вероятности необнаруженной ошибки,будем считать, что в среднем 85% кодовых слов принимается верно2.4- Свойства линейных блоковых кодовбез переспроса.
Учитывая также, что доля информационных бит вкодовом слове равна k/п получаем, что при скорости передачи Яьэффективная скорость равнак _•4 • 0,85 • 16 кбит/сек _ _ ,. ,!Rb,eff = -PcRb «=« 7,77 кбит/сек..(2.36)Замечание. Выбранное в примере SNR, равное 6 дВ, приводит кнедопустимо высокой вероятности ошибки на бит. Недопустимовысокими являются также потери эффективной* скорости передачи.4. Пропускная способность ДСК без памяти была рассмотрена в первой части этой книги. При вероятности ошибки двоичного символае, равной е = Ре, пропускная способность канала на один передаваемый двоичный символ составляетС д с к = 1 бит - Нь{е) = 0,842 бит.(2.37)При заданной скорости 1& кбит/сек максимально достижимая эффективная скорость передачи информации с пренебрежимо малойвероятностью ошибки равнаЛтах < 13,4 кбит/сек,(2.38)что почти в два раза превышает величину из (2.36).В рассмотренном примере мы использовали зависимость вероятности ошибочного бита от соотношения сигнал/шум (SNR) при передаче данных по каналу с АБГШ.
Здесь мы сталкиваемся с «энергетическим» аспектом цифровой передачи информации. Рассмотримэтот аспект более подробно.Будем исходить из постоянства некоторых параметров передачи.Пусть этими параметрами являются эффективная скорость передачи данных и средняя мощность передатчика. Пусть, далее, передачаинформации осуществляется по каналу с аддитивным белым гауссовским шумом (АБГШ) и прием информации производится с применением согласованных фильтров. В таком канале SNR оказывается пропорциональным длительности двоичного символа, поэтому,при" постоянной мощности передатчика переход от четырех двоичных символов (передача без кодирования) к семи символам ((7,4)-кодХэмминга ) внутри фиксированного интервала времени эквивалентен уменьшению SNR в 7/4 раза, что равно, приблизительно, 2,4 дБ.Глава 2.
Линейные блоковые кодыИ, наоборот, SNR на один двоичный символ при передаче без кодирования на 2,4 дБ выше, чем при использовании (7,4)-кода Хэммингаи составляет, в нашем случае, 8,4 дБ. (Здесь мы даже не учитываем вероятность переспроса при передаче с кодированием). Согласно(2.32), SNR, равному 8,4 дБ, соответствует вероятность ошибки набит, равная Рь = 0,0043. Отсюда, вероятность безошибочной передачи блока, содержащего 4 информационных символа, составляетРс = (1 - 0,0043)4 = 0,98.(2.39)Отметим, что при постоянной мощности передатчика, применяякодирование, мы увеличиваем вероятность ошибки двоичного символа (в нашем случае от 0,0043 до 0,023).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
