Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

13. О кодах, исправляющих несимметричные ошибки

На практике нередко встречаются каналы, отличающиеся асимметричным характером ошибок, скажем, такие, в которых преобладают замещения вида 0 → 1 (т. е. вместо нуля принимается единица), а замещения 1 → 0 крайне редки.

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

Исходное соображение здесь очень простое: если в канале невозможны ошибки вида 1 → 0, то в принятом двоичном слове нет нужды проверять позиции с нулевыми символами - они наверняка переданы без искажений. Будем поэтому производить проверку таким образом, чтобы ее результат зависел только от позиций с единичными символами, точнее, от номеров этих позиций. С этой целью для произвольного двоичного слова u = х1х2 ... хn составим сумму

S(u) = #8721;ni=1 xii. (1)

В сумме (1) ненулевые слагаемые соответствуют только единичным символам и каждое из них совпадает с номером этого символа, т. е. число S(u) равно сумме номеров единичных позиций слова u.

Как обычно, постараемся найти простое условие, выделяющее кодовые слова среди прочих. Будем искать это условие в виде сравнения по некоторому модулю l. Представим себе, что число l уже выбрано, и рассмотрим код, состоящий из всех таких слов υ = x1 х2 ... хn, для которых

S(υ) ≡ 0 (mod l), (2)

т. е. из слов, для которых сумма номеров единичных позиций делится на l без остатка. Обозначим указанный код через Vn, l. Так, при n = 4, l = 5 получим следующее множество кодовых слов:

V4,5 = {0000, 1001, 0110, 1111}.

Нетрудно убедиться, хотя бы перебором всех возможных случаев, что данный код исправляет любые одиночные ошибки вида 0 → 1. Например, ошибка в третьем символе слова 1001 переводит его в слово 1011. При этом никакое другое кодовое слово не могло преобразоваться в результате одиночной ошибки в слово 1011. Поэтому получатель декодирует слово 1011 однозначно, считая, что было послано слово 1001. Аналогично обстоит дело с другими двоичными наборами, содержащими одиночные замещения нуля на единицу. Отметим, что в некоторых случаях (но не всегда!) возможно исправление также и двойных замещений нуля на единицу. Один из таких случаев - ошибка в двух первых символах слова 0000. Получающееся при этом слово 1100 не является кодовым и не могло получиться ни из какого кодового слова в результате одиночной ошибки. К тому же имеется единственный вариант двойного замещения, переводящего кодовое слово в слово 1100, - именно тот, который был указан выше.

Подобные свойства сохраняются и для произвольного кода Vn,l, если l ≥ n + 1. В частности, такой код исправляет любые одиночные ошибки вида 0 → 1; при этом алгоритм их исправления чрезвычайно прост. Действительно, пусть в кодовом слове υ = x1 x2 ... xn произошло не более одной ошибки и получилось слово u. Если ошибка произошла в j-м символе, то понятно, что S(u) = S(υ) + j. Поскольку S(υ) ≡ 0 (mod l), то вычет числа S (и) по модулю l равен j, т. е. номеру позиции, в которой произошла ошибка. Если же ошибки не произошло, то вычет S(u) по модулю l равен нулю.

Проиллюстрируем исправление одиночной ошибки на примере рассмотренного выше кода V4,5. Пусть принято слово u = 0111. Тогда S(u) = 2 + 3 + 4 = 9 ≡ 4 (mod 5). Следовательно, ошибка произошла в четвертой позиции, т. е. передавалось кодовое слово 0110.

Наиболее употребимы коды Vn,l при минимально возможном l : l = n + 1. Именно они впервые были предложены советскими специалистами по кодированию Р. Р. Варшамовым и Г. М. Тененгольцем.

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

Предположим, что в некотором слове υ = x1x2 ... хn произошло выпадение одного символа, в результате чего получилось слово u = у1у2 ... yn-1 длины n-1. Пусть n1 - число единиц, а n0 - число нулей, расположенных правее выпавшего символа. Оказывается, числа n1 и n0 могут быть определены с помощью суммы

S(u) = ∑n-1i=1 iyi.

В самом деле, если выпал символ 0, то S(υ) - S(u) = n1, а если выпал символ 1, то S(υ) - S(u) = n - n0. Если ω(u) - вес слова u, то, очевидно,

n1 ≤ ω(u) < n - n0 ≤ n. (3)

Так как S(u) ≡ 0 (mod l), то вычет числа - S(u) по модулю l равен либо n1 (в случае выпадения нуля), либо n - n0 (в случае выпадения единицы). Неравенства (3) показывают, что если этот вычет не превосходит ω(u), то выпал символ 0, если же это не так, то символ 1. В первом случае выпавший символ 0 надо вставить в слово и так, чтобы правее него было число единиц, равное вычету числа - S(u) по модулю l. Если же этот вычет больше, чем ω(u), то вставляем в слово и единицу так, чтобы правее нее было число нулей, равное разности п и вычета числа - S(u). Если, например, при использовании кода V4,5 принято слово u = 101, то S(u) = 4, a ω(u) = 2, вычет числа - S(u) по модулю 5 равен 1, и, следовательно, выпал символ 0. Вставить его надо так, чтобы правее него была одна единица. Получается кодовое слово 1001.

Аналогично исследуется случай одиночной вставки символа. Читателю предлагается обосновать следующий алгоритм восстановления кодового слова, отвечающий этому случаю.

Пусть принято слово u = y1y2 ... yn+1 длины n + 1 и k - вычет числа S(u) по модулю l. Тогда

1) если k = 0, то отбрасывается последний символ слова u;

2) если 0 < k < ω(u), то отбрасывается любой нулевой символ, правее которого в слове u ровно k единиц;

3) если k = ω(u), отбрасывается первый символ слова u;

4) если k > ω(u), отбрасывается любой единичный символ, правее которого имеется n + 1 - k нулей.

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru