Помехозащитное кодирование в двоичном симметричном канале.

Простейший код для борьбы с шумом это контроль четности, он, в частности, широко используется в модемах. Кодирование заключает­ся в добавлении к каждому байту девятого бита таким образом, чтобы дополнить количество единиц в байте до заранее выбранного для кода четного (even) или нечетного (odd) значения. Используя этот код, можно лишь обнаруживать большинство ошибок.

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

Двоичный симметричный канал изображен на рис, 13, где р это вероятность безошибочной передачи бита, a q вероятность передачи би­та с ошибкой. Предполагается, что в таком канале ошибки происходят независимо. Далее рассматри­ваются только такие каналы.

 

 

Двоичный симметричный канал реализует схему Бернулли, поэто­му вероятность передачи nбит по двоичному симметричному каналу с kошибками равна .

Пример. Вероятность передачи одного бита информации с ошибкой равна q= 0.01 и нас интересует вероятность безошибочной передачи 1000 бит (125 байт). Искомую вероятность можно подсчитать по фор­муле Р₁₀₀₀(0) =  4.32* 10^-5, т.е. она ничтожно мала.

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

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

Простой код с обнаружением ошибок основан на схеме проверки четности, применимой к сообщениям а₁ ... а _т любой фиксированной длины т.. Схема кодирования определяется следующими формулами:

 

 

таким образом, должна быть четной.

Соответствующая схема декодирования тривиальна:

 

 

Разумеется, что четность не гарантирует безошибочной пере­дачи.

Пример. Проверки четности при т = 2 реализуется следующим кодом (функцией Е): 00→000, 01→011, 10→101, 11→110. В двоич­ном симметричном канале доля неверно принятых сообщений для этого кода (хотя бы с одной ошибкой) равна q ³ +3 pq ²+3p²q (три, две или одна ошибка соответственно). Из них незамеченными окажутся только ошибки точно в двух битах, не изменяющие четности. Вероятность та­ких ошибок 3 pq ² . Вероятность ошибочной передачи сообщения из двух битов равна 2 pq + q ² . При малых q верно, что 3 pq ² « 2 pq +q².

Рассмотрим (m,Зm)-код с тройным повторением. Коды с повто­рениями очень неэффективны, но полезны в качестве теоретического примера кодов, исправляющих ошибки. Любое сообщение разбивается на блоки длиной mкаждое и каждый блок передается трижды что определяет функцию E. Функция D определяется следующим образом. Принятая строка разбивается на блоки длиной 3m. Бит с номером i (1 ≤  i ≤ m) в декодированном блоке получается из анализа битов с но­мерами i, i+m, i +2 m в полученном блоке: берется тот бит из трех, кото­рый встречается не менее двух paз. Вероятность того, что бит в данной позиции будет принят трижды правильно равна р³. Вероятность одной ошибки в тропке равна 3p ² q . Поэтому вероятность правильного прие­ма одного бита равна р³ + 3 p ² q . Аналогичным образом получается, что вероятность приема ошибочного бита равна q³ + 3 pq ² .

Пример. Предположим q = 0,1. Тогда вероятность ошибки при передачи одного бита 0,028, т.е. этот код снижает вероятность ошибки с 10% до 2,8%. Подобным образом организованная передача с пятикрат­ным повторением даст вероятность ошибки на бит

 

 

т.е. менее 1%. В результате вероятность правильной передачи стро­ки длиной 10 возрастет с 0,9¹⁰ ≈ 35% до 0,972¹⁰ ≈ 75% при тройных повторениях и до 0,99144¹⁰ ≈ 92% при пятикратных повторениях.

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

Рассмотрим (2048, 2313)-код, используемый при записи данных на магнитофонную ленту компьютерами Apple II, К каждому байту ис­ходных данных прибавляется бит четности и, кроме того, после каж­дых таких расширенных битом четности 256 байт добавляется специ­альный байт, также расширенный битом четности. Этот специальный байт, который называют контрольной суммой, (check sum), есть результат применения поразрядной логической операции "исключающее ИЛИ" (XOR) к 256 предшествующим расширенным байтам. Этот код способен как обнаруживать ошибки нечетной кратности в каждом из отдельных байтов, так и исправлять до 8 ошибок в блоке длиной 256 байт. Исправление ошибок основано на том, что если в одном из бит одного из байт 256 байтового блока произойдет сбой, обнаруживаемый проверкой четности, то этот же сбой проявится и в том, что результат операции "исключающее ИЛИ" над всеми соответствующими битами блока не будет соответствовать соответствующему биту контрольной суммы. Сбойный бит однозначно определяется пересечением сбойных колонки байта и строки бита контрольной суммы. На рис. 15 изобра­жена схема участка ленты, содержащего ровно 9 ошибок в позициях.

обозначенных р₁, р₂,.....,р₉. Расширенный байт контрольной суммы

обозначен CS,a бит паритета (в данном случае четности) РВ (parity bit). Ошибка в позиции р₁ может быть исправлена. Ошибки в по позициях р₄, р₅, р₆, р₇ ,можно обнаружить, но не исправить. Ошибки в позициях р₂, р₃, р₈, р₉, невозможно даже обнаружить.

 

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

Расстоянием (Хэмминга) между двоичными словами длины nна­зывается количество позиций, в которых эти слова различаются. Это одно из ключевых понятий теории кодирования. Если обозначить двоичные слова как а=а₁…а _n и b = b ₁ … b_n , то расстояние между ними обозначается d ( a , b ).

Весом двоичного слова = а=а₁…а _n , называется количество единиц в нем. Обозначение u(а). Можно сказать, что

Пример. Пусть а = 1001 и b = 0011, тогда u ( a ) = u ( b ) = 2, d ( a , b ) = 2.

Далее операция + при применении к двоичным словам будет озна­чать поразрядное сложение без переноса, т.е. сложение по модулю 2 или "исключающее ИЛ И" (XOR).

Расстояние, между двоичными словами а и b равно весу их пораз­рядной суммы, т.е. d ( a , b ) = и(а +b).

Если два слова различаются в каком-либо разряде, то это добавит единицу к весу их поразрядной суммы.

Следовательно, если а и b слова длины,то вероятность того, что слово а будет принято как b,равна

Например, вероятность того, что слово 1011 будет принято как 0011, равна p ³ q .

Для возможности обнаружения ошибки в одной позиции минималь­ное расстояние между словами кода должно быть большим 1.

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

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

Достаточность доказывается конструктивно: если условие утверждения выполнено на Е, то в качестве декодирующей функции D следует взять функ­цию, сообщающую об ошибке, если декодируемое слово отличается от любого из слов из образа Е. Необходимость доказывается от противного: если мини­мальное расстояние к^’ < к + 1, то ошибка в к^! позициях сможет превратить одно кодовое слово в другое.

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

≈ (при малых q и не слишком маленьких k

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

Достаточность доказывается конструктивно: если условие утверждения выполнено на Е, то в качестве декодирующей функции D следует взять функ­цию, возвращающую ближайшее к декодируемому слово из образа Е. Необхо­димость доказывается от противного. Пусть расстояние между выбранными словами в коде равно 2k. Тогда если при передаче каждого из этих слов слу­чится к ошибок, которые изменят биты, в которых различаются эти слова, то

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

Пример. Рассмотрим (1.3)-код, состоящий из Е, задающей отобра­жение 0→ 000 и 1→111, и D , задающей отображение 000 →0,001→0,010→0,011→1,100→ 0,101→1,110→1,111→1. Этот код (с тройным повторением) исправляет ошибки в одной позиции, т.к. мини­мальное расстояние между словами кода равно 3.

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

Передачу данных часто удобно рассматривать следующим образом. Пусть исходное сообщение а=а₁…а _m кодируется функцией Е в кодовое слово b = b ₁ … b_n .Канал связи при передаче добавляет к нему функцией Т строку ошибок е = е₁…е _n так, что приемник получает сообщение r = r ₁ .. . r_n где r_i = b_i + e_i (1≤ i ≤ n ), Система, исправ­ляющая ошибки, переводит rв некоторое (обычно ближайшее) кодовое слово. Система, только обнаруживающая ошибки, лишь проверяет, яв­ляется ли принятое слово кодовым, и сигнализирует о наличии ошибки, если что не так.

Пример. Пусть передаваемое слово а = 01 кодируется словом b= 0110, а строка ошибок е = 0010. Тогда будет принято слово r = 0100. Система, исправляющая ошибки, переведет его в 0110 и затем восстановит переданное слово 01.

Eсли система только обнаруживает ошибки и расстояние между любыми кодовыми словами k ≥ 2, то любая строка ошибок е с един­ственной единицей приведет к слову r = b + e . которое не является кодовым.

Пример. Рассмотрим (2, 3)- код с проверкой четности. Множество кодовых слов {000, 011, 101,110}. Ни одна изстрок ошибок 001, 010, 101, 111 не переводит одно кодовое слово в другое. Поэтому однократная и тройная ошибки могут быть обнаружены.

Пример. Следующий (2,5)-код обнаруживает две ошибки:

 

 

Этот же код способен исправлять однократную ошибку, потому что любые два кодовых слова отличаются по меньшей мере в трех позициях. Из того, что d ( b_i , bj ) ≥ 3 при i ≠ j, следует, что однократная ошибка приведет к приему слова, которое находится на расстоянии 1 от кодового слова, которое было передано. Поэтому схема декодирова­ния, состоящая в том, что принятое слово переводится в ближайшее к нему кодовое, будет исправлять однократную ошибку. В двоичном симметричном канале вероятность правильной передачи одного блока будет не меньше чем р⁵ +5р⁴ q

Установлено (20), что в (п – r , n )- коде, минимальное расстояние между кодовыми словами которого 2 k +1, числа n , r (число допол­нительных разрядов в кодовых словах) и kдолжны соответствовать неравенству

называемому  неравенством или нижней границей Хэмминга. Кроме того, если числа n, rи kсоответствуют неравенству

называемому неравенством или верхней границей Варшамова-Гильберта, то существует (п – r , n )- код, исправляющий все ошибки веса kи менее [20].

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

 

---

Дата добавления: 2022-01-22; просмотров: 74; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!