Помехоустойчивое кодирование

Пример. Рассмотрим код, состоящий из четырех кодовых слов 00000, 00111, 11100 и 11011. Каждое кодовое слово используется для представления одного из четырех возможных в сообщении. Поскольку код включает лишь небольшую долю всех 32 возможных последовательностей из пяти символов, можно выбрать кодовые слова таким образом, чтобы каждые два из них отличались друг от друга не менее чем в трех позициях. Таким образом, кодовое расстояние равно трем и код может исправлять одиночную ошибку в любой позиции. Чтобы провести процедуру декодирования при этом коде, каждой из 28 недопустимых последовательностей нужно поставить в соответствие ближайшую к ней допустимую последовательность. Этот процесс ведет к созданию таблицы декодирования, которая строится следующим образом. Вначале под каждым кодовым словом выписываются все возможные последовательности, отличающиеся от него в одной позиции. В результате получается часть табл. 2, заключенная между штриховыми линиями. Нужно заметить, что после построения этой части осталось восемь последовательностей. Каждая из этих последовательностей отличается от каждого кодового слова не менее чем в двух позициях. Однако в отличие от других последовательностей эти восемь последовательностей нельзя однозначно разместить в таблице. Например, последовательностью можно поместить либо в первый, либо в четвертый столбец. При использовании этой таблицы в процессе декодирования нужно найти столбец, в котором содержится принятая последовательность, и а качестве выходной последовательности декодера взять кодовое слово, находящееся в верхней строке этого столбца.

 

Таблица 2. Таблица декодирования для кода с четырьмя словами

00000	11100	01111	11011
10000	01100	10111	01011
01000	10100	01111	10011
00100	11000	00011	11111
00010	11110	00101	11001
00001	11101	00110	11010
10001	01101	10110	01010
10010	01110	10101	01001

 

Причина, по которой таблица декодирования  должна строиться именно таким образом, очень проста. Вероятность появления фиксированной комбинации из i ошибок равна Р^t_e(1 -Р_e)^5-i. Необходимо отметить что при Р_e<1/2 (1 -Р_e)⁵P_e(1 -Р_e)⁴Р_e²(1 -Р_e)³...

Таким образом, появление фиксированной  одиночной ошибки более вероятно, чем фиксированной комбинации двух ошибок, и т. д. Это значит, что  декодер, который декодирует каждую принятую последовательность в ближайшее к ней по расстоянию Хемминга кодовое слово, выбирает в действительности то кодовое слово, вероятность передачи которого максимальна (в предположении, что все кодовые слова равновероятны). Декодер, реализующий это правило декодирования, является декодером максимального правдоподобия, и в указанных предположениях он минимизирует вероятность появления ошибки декодирования принятой последовательности. В этом смысле такой декодер является оптимальным. Это понятие очень важно, поскольку декодеры максимального правдоподобия часто используются для коротких кодов. Кроме того, параметры декодера максимального правдоподобия могут служить эталоном, с которым сравниваются параметры других, неоптимальных декодеров. Если декодирование ведется с помощью таблицы декодирования, то элементы таблицы можно расположить так, чтобы получить декодирование по максимуму правдоподобия. К сожалению, объем таблицы растет экспоненциально с ростом длины блока, так что использование таблицы декодирования для длинных кодов нецелесообразно. Однако таблица декодирования часто оказывается полезной для выяснения важных свойств блоковых кодов.

Множество кодовых слов в таблице  декодирования является подмножеством (первой строкой таблицы декодирования) множества всех 2ⁿ последовательностей длиной n. В процессе построения таблицы декодирования множество всех последовательностей длиной n разбивается на непересекающиеся подмножества (столбцы таблицы декодирования). В случае, когда код исправляет t ошибок, число N_e последовательностей длиной n в каждом подмножестве удовлетворяет неравенству

N_e>=1+n+C_n²+...+C_n^t, (2)

где C_nⁱ - i-й биномиальный коэффициент.

Неравенство (2) следует непосредственно  из того, что имеется ровно n различных  последовательностей, отличающихся от данной последовательности в одной позиции, C_n² последовательностей, отличающихся в двух позициях, и т. д. Как и в приведенном выше простом примере, после размещения всех последовательностей, отличающихся от кодовых в t или менее позициях, почти всегда остаются неразмещенные последовательности [отсюда неравенство в (2)]. Теперь можно связать избыточность кода c числом ошибок, которые им исправляются Заметим сначала, что число всех возможных последовательностей равно 2ⁿ. Каждый столбец таблицы декодирования содержит N_e таких последовательностей, поэтому общее число кодовых слов должно удовлетворять неравенству N_e<=<2ⁿ/(1+n+C_n²+...+C_n^t), (3)

Это неравенство называется границей Хемминга или границей сферической  упаковки. Равенство в (3) достигается только для так называемых совершенных кодов. Эти коды исправляют все наборы из t или менее ошибок и не исправляют никаких других наборов. Число известных совершенных кодов очень невелико, так что равенство в (1.3) достигается в очень редких случаях.

Процесс кодирования состоит в  том, что наборы k информационных символов отображаются в кодовые последовательности, состоящие из n символов. Любое такое отображение будем называть (n, k)-кодом, хотя обычно такое название применяется только к линейным кодам (которые обсуждаются позже). Поскольку число последовательностей длиной k равно 2^k, неравенство (3) можно переписать следующим образом:

2^k<=2ⁿ/(1+n+C_n²+...+C_n^t), (4)

Мера эффективности кода определяется отношением R=k/n (5)

и называется скоростью кода. Доля избыточно передаваемых символов равна 1-R.

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

 

Таблица 3. Таблица поиска при декодировании

Входная последовательность	Кодовая последовательность
00	00100
01	01111
10	11011
11	1000

 

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

Существует много хороших конструктивных методов кодирования, позволяющих  исправлять кратные ошибки и приводящих к заметному уменьшению частоты появления ошибочных символов. Эти коды легко строятся и с помощью современных полупроводниковых устройств относительно просто декодируются. Например, существует блоковый код длиной 40, содержащий 50% избыточных символов и позволяющий исправлять четыре случайные ошибки. На рис. 2 показано, что при Р_e=0,01 этот код имеет вероятность ошибки блока, меньшую 10^-4. Если этого недостаточно, разработчик увеличивает избыточность, чтобы исправлять большее число ошибок, или переходит к кодам с большей длиной блока и получает выигрыш за счет большего усреднения. В каждом случае нужно принимать во внимание возникающие дополнительные затраты. Однако обе указанные возможности допустимы и могут представлять практически приемлемые альтернативы. Прежде чем идти дальше, сделаем небольшое отступление, которое не имеет большого практического значения, но привлекает внимание специалистов по теории кодирования в течение многих лет. Форма кривых, изображенных на рис. 2, позволяет предположить, что если имеется схема, исправляющая фиксированную долю t/n ошибочных символов в блоке (в нашем случае t/n незначительно превышает 0,01), то, выбирая длину блока достаточно большой, можно сделать долю ошибок сколь угодно малой. К сожалению, это оказывается очень трудной задачей. Большинство конструктивных процедур может обеспечить постоянное отношение t/n лишь при возрастающей доле избыточных символов (другими словами, R≥0 при n≥∞). Таким образом, потеря эффективности возникает из-за того, что доля полезных сообщений становится очень малой при большой длине блока. Частично эта задача была решена Юстесеном в 1972 г. Юстесен показал, что можно построить класс асимптотически хороших (в указанном здесь смысле) кодов и указать для них процедуру декодирования. Однако, насколько известно, эти коды не применялись ни в одной из существующих систем связи.

 

1.3. Основные  параметры помехоустойчивых кодов

 

 

 Проблема повышения верности обусловлена не соответствием между требованиями, предъявляемыми при передаче данных, и качеством реальных каналов связи. В сетях передачи данных требуется обеспечить верность не хуже 10^-6– 10^-9, а при использовании реальных каналов связи и простого (первичного) кода указанная верность не превышает 10^-2–10^-5.

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

Простые коды характеризуются тем, что для  передачи информации используются все  кодовые слова (комбинации), количество которых равно N=qⁿ (q – основание кода, а n – длина кода). В общем случае они могут отличаться друг от друга одним символом (элементом). Поэтому даже один ошибочно принятый символ приводит к замене одного кодового слова другим и, следовательно, к неправильному приему сообщения в целом.

Помехоустойчивыми называются коды, позволяющие обнаруживать и (или) исправлять ошибки в кодовых  словах, которые возникают при передаче по каналам связи. Эти коды строятся таким образом, что для передачи сообщения используется лишь часть кодовых слов, которые отличаются друг от друга более чем в одном символе. Эти кодовые слова называются разрешенными. Все остальные кодовые слова не используются и относятся к числу запрещенных.

Применение  помехоустойчивых кодов для повышения  верности передачи данных связанно с решением задач кодирования и декодирования.

Задача  кодирования заключается в получении  при передаче для каждой k – элементной комбинации из множества q^k соответствующего ей кодового слова длиною n из множества qⁿ.

Задача  декодирования состоит в получении k – элементной комбинации из принятого n – разрядного кодового слова при одновременном обнаружении или исправлении ошибок.

Основные  параметры помехоустойчивых кодов:

• Длина кода – n;
• Длина информационной последовательности – k;
• Длина проверочной последовательности – r=n-k;
• Кодовое расстояние кода – d₀;
• Скорость кода – R=k/n;
• Избыточность кода - R¢;
• Вероятность обнаружения ошибки (искажения) – Р_ОО;
• Вероятность не обнаружения ошибки (искажения) – Р_НО.

Кодовое расстояние между двумя  кодовыми словами (расстояние Хэмминга) – это число позиций, в которых они отличаются друг от друга.

Кодовое расстояние кода – это наименьшее расстояние Хэмминга между различными парами кодовых слов.

Основные  зависимости между кратностью обнаруживаемых ошибок t₀, исправляемых ошибок t_u, исправлением стираний t_c и кодовым расстоянием d₀ кода:

Стиранием называется «потеря» значения передаваемого символа в некоторой позиции кодового слова, которая известна.

Код, в котором каждое кодовое  слово начинается с информационных символов и заканчивается проверочными символами, называется систематическим.

Граничные соотношения между параметрами  помехоустойчивых кодов

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

Существуют  граничные оценки, связывающие d₀, n и k.

Граница Хэмминга, которая близка к оптимальной, для высокоскоростных кодов, определяется соотношениями:

для q-ного кода      

для двоичного кода    

Граница Плоткина, которую целесообразно использовать для низкоскоростных кодов определяется соотношениями:

для q-ного кода     

для двоичного кода    

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

Граница Варшамова-Гильберта (нижняя граница), определяемая соотношениями:

     

и

показывает, при каком значении n-k определено существует код, гарантийно исправляющий ошибки кратности t_u.

 

 

 

 

ВЫВОДЫ ПО 1 ГЛАВЕ

 

В первой главе данной работы были приведены основные сведения о помехоустойчивом кодировании.

Первый пункт посвящен понятию  «помехоустойчивость». Это способность системы осуществлять прием информации в условиях наличия помех в линии связи и искажений во внутри аппаратных трактах. Помехоустойчивость обеспечивает надежность и достоверность передаваемой информации (данных).

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