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

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

Теория помехоустойчивого кодирования информации развивается с 1946 года, после опубликования американским ученым К.Шенноном фундаментальной теоремы теории информации, известной как основная теорема кодирования К.Шеннона. Для дискретного канала теорема формулируется следующим образом: если производительность источника сообщений Н'(A) меньше пропускной способности канала С, т.е. Н'(A)<C, то существует способ кодирования, при котором вероятность ошибочного декодирования может быть сколь угодно мала. Если же Н'(A)≥C, то таких способов не существует.

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

Наиболее простым способом реализации помехоустойчивого кодирования является метод многократной передачи либо каждого информационного символа, либо всего блока в целом (кратность передачи ≥3). Решение о каждом принятом символе принимается по большинству одинаковых символов. Например:

10110 -	передаваемое сообщение,
10010 -	принятое сообщение при первой передаче,
10100 -	принятое сообщение при повторной передаче,
00110 -	принятое сообщение при третьей передаче,
10110 -	восстановленное сообщение.

Этот способ обладает высокой избыточностью, что резко уменьшает скорость передачи информации по каналу связи.

Более эффективным является метод, при котором все множество возможных комбинаций, принимаемых декодером, разбивается на две части. В одну часть входят разрешенные кодовые комбинации (слова), формируемые кодером, а в другую - запрещенные кодовые комбинации, в которые могут перейти разрешенные кодовые слова под воздействием помех. Для реализации этого метода необходимо использовать избыточный код − код, в котором для кодирования используют только часть возможных кодовых комбинаций, называемых разрешенными: М_разр<М_общ. Остальные комбинации считают запрещенными.

Простой (примитивный) код, в котором для кодирования задействованы все возможные кодовые комбинации, не может обеспечить помехоустойчивого кодирования, так как в этом случае М_раз= М_общ=mⁿ, где m -основание кода; n -число разрядов в кодовом слове. Избыточный код формируют из простого кода путем введения определенным образом дополнительных проверочных символов в исходную информационную кодовую комбинацию.

Пример 3. Для передачи двух сообщений простым двоичным кодом достаточно использовать одноразрядный код, поскольку при этом число возможных кодовых комбинаций М_общ=2ⁿ=2¹=2. Одному из исходных сообщений присваивается символ " 0 ", а другому − символ " 1 ". Если при передаче любого из сообщений произойдет ошибка (" 1 " перейдет в "0 " или наоборот), то ее невозможно обнаружить, так как и " 0 " и " 1 " являются разрешенными комбинациями. Если же ввести в кодовые слова по два дополнительных символа, код станет трехразрядным (n=3) и число возможных комбинаций увеличится до восьми (М_общ=2³=8). Для передачи двух исходных сообщений выбирают из этих восьми возможных только две разрешенные комбинации, максимально отличающиеся друг от друга. Очевидно, что ими должны быть 000 и 111 или 001 и 110 и т.д. Благодаря введенной избыточности, одна и даже две ошибки, возникшие при передаче любого из двух сообщений, переводят разрешенную кодовую комбинацию в запрещенную, и будут обнаружены. Трехкратная ошибка в данном случае не обнаруживается, так как передаваемая разрешенная комбинация в результате трех ошибок переходит в другую разрешенную комбинацию.

Рассмотрим подробнее работу кодера и декодера (кодека) помехоустойчивого двоичного кода в системе передачи дискретных сообщений. Структурная схема включения помехоустойчивого кодека в тракт передачи приведена на рисунке 3 (устройству «Дискретный канал передачи» на рисунке 3 соответствует совокупность трех устройств на рисунке 1, а именно: линейного кодера, линии передачи и линейного декодера).

Рисунок 3 ─ Электрическая структурная схема включения помехоустойчивого кодека в тракт передачи

На вход кодера поступает безызбыточная кодовая комбинация А_k, состоящая из k двоичных информационных сигналов а, а₂…а_k. При этом возможное число входных комбинаций не превышает 2^k. Кодер из принятых k символов по определенному правилу формирует r дополнительных проверочных символов и выдает на выход n -разрядную разрешенную кодовую комбинацию В с символами b₁b₂…b_k…b_n, где n -общее число символов в кодовом слове (n=k+r). Поскольку n > k, то увеличивается общее число возможных комбинаций:

М_общ =2ⁿ=2^{k+ r} (1)

Кодер формирует только разрешенные кодовые комбинации, причем их максимальное число М_разр равно числу входных комбинаций. Таким образом, благодаря введению дополнительных поверочных символов r, стало возможным разделение всего множества возможных комбинаций на разрешенные и запрещенные:

М_запр= М_общ - М_разр (2)

Принятая декодером n -разрядная кодовая последовательность В^* () обозначается со звездочкой, так как в результате воздействия помех она может в любом разряде отличаться от переданной кодовой комбинации В. В декодере комбинация сравнивается со всеми разрешенными для данного кода комбинациями. Если установлено, что принята разрешенная комбинация, то декодер формирует и выдает на выход k -разрядную последовательность информационных символов , которая может совпадать с исходной комбинацией А_k (ошибка отсутствует) или не совпадать (под воздействием помехи разрешенная кодовая комбинация перешла в другую разрешенную). Если же принята запрещенная комбинация, то декодер обнаруживает наличие ошибки. Необходимым условием обнаружения ошибки является переход разрешенной кодовой комбинации в одну из запрещенных.

Существует два алгоритма декодирования помехоустойчивых кодов: с обнаружением ошибок и с исправлением ошибок. В первом случае при обнаружении ошибки декодер не выдает получателю заведомо ошибочную последовательность из k символов, а по цепи обратной связи направляет в передатчик запрос на повторную передачу сообщения. Если в системе передачи не предусмотрена обратная связь, то используются другие возможности. Например, в телевидении взамен ошибочно принятого демонстрируют предыдущий кадр изображения или на экране телевизора отображается информация «Нет сигнала» и т.д.

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

Степень различия между кодовыми комбинациями оценивается расстоянием Хэмминга (d, d_х). Для любых двух двоичных комбинаций символов A_i и A_j расстояние Хэмминга d_ij равно числу несовпадающих в них разрядов и математически вычисляется как число единиц в сумме по модулю два этих комбинаций. Так, приведенные ниже две последовательности A_i и A_j не совпадают в трех разрядах:

101000= Ai 110010= Aj

В этом случае d_ij=d=3.

Для оценки корректирующей способности заданного кода используют минимальное расстояние Хэмминга, взятое по всем парам слов. Его называют кодовое расстояние d₀:

d₀=min d_ij = d_min.

Если для какого-то кода расстояния Хэмминга принимают значения 6,3,7,5,4, то кодовое расстояние этого кода d₀ = d_min =3. С позиции теории кодирования d₀ показывает, сколько символов в разрешенной кодовой комбинации надо исказить, чтобы перевести её в другую разрешенную последовательность.

Дата добавления: 2015-08-13