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

Оглавление

История кодирования, контролирующего ошибки 2

Приложения 5

Общие сведения о кодах и системах кодированной связи 7

Мешающие влияния в каналах связи 13

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

Пример. 21

Краткая классификация 23

Практика кодирования 31

Код Хэмминга 40

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

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

По сути, помехоустойчивое кодирование — это добавление к исходной информации дополнительной, проверочной, информации. Для кодирования на передающей стороне используются кодер, а на принимающей стороне — используют декодер для получения исходного сообщения.

История кодирования, контролирующего ошибки

История кодирования, контролирующего  ошибки, началась в 1948 г. публикацией  знаменитой статьи Клода Шеннона. Шеннон показал, что с каждым каналом  связано измеряемое в битах в  секунду и называемое пропускной способностью канала число С, имеющее следующее значение. Если требуемая от системы связи скорость передачи информации R (измеряемая в битах в секунду) меньше С, то, используя коды, контролирующие ошибки, для данного канала можно построить такую систему связи, что вероятность ошибки на выходе будет сколь угодно мала. В самом деле, из шенноновской теории информации следует тот важный вывод, что построение слишком хороших каналов является расточительством; экономически выгоднее использовать кодирование. Фактически в работе Шеннона утверждается, что мощность сигнала, шум в канале и полоса частот ограничивают лишь скорость передачи, а не ее точность. Шеннон, однако, не указал, как найти подходящие коды, а лишь доказал их существование. В пятидесятые годы много усилий было потрачено на попытки построения в явном виде классов кодов, позволяющих получить обещанную сколь угодно малую вероятность ошибки, но результаты были скудными. В следующем десятилетии решению этой увлекательной задачи уделялось меньше внимания; вместо этого исследователи кодов предприняли длительную атаку по двум основным направлениям.

Первое направление носило чисто алгебраический характер и  преимущественно рассматривало  блоковые коды. Первые блоковые коды были введены в 1950 г., когда Хэмминг  описал класс блоковых кодов, исправляющих одиночные ошибки. Коды Хэмминга были разочаровывающе слабы по сравнению с обещанными Шенноном гораздо более сильными кодами. Несмотря на усиленные исследования, до конца пятидесятых годов не было построено лучшего класса кодов. В течение этого периода без какой-либо общей теории были найдены многие коды с малой длиной блока. Основной сдвиг произошел, когда Боуз и Рой-Чоудхури [1960] и Хоквингем [1959] нашли большой класс кодов, исправляющих кратные ошибки (коды БЧХ), а Рид и Соломон [1960] нашли связанный с кодами БЧХ класс кодов для недвоичных каналов. Хотя эти коды остаются среди наиболее важных классов кодов, общая теория блоковых кодов, контролирующих ошибки, с тех пор успешно развивалась.

Открытие кодов БЧХ  привело к поиску практических методов  построения жестких или мягких реализации кодеров и декодеров. Первый хороший  алгоритм был предложен Питерсоном. Впоследствии мощный алгоритм выполнения описанных Питерсоном вычислений был  предложен Берлекэмпом и Месси, и их реализация вошла в практику как только стала доступной новая цифровая техника. Второе направление исследований по кодированию носило скорее вероятностный характер. Ранние исследования были свя-заны с оценками вероятностей ошибки для лучших семейств блоковых кодов, несмотря на то, что эти лучшие коды не были известны. С этими исследованиями были связаны попытки понять кодирование и декодирование с вероятностной точки зрения, и эти попытки привели к появлению последовательного декодирования. В последовательном декодировании вводится класс неблоковых кодов бесконечной длины, которые можно описать деревом и декодировать с помощью алгоритмов поиска по дереву. Наиболее полезными древовидными кодами являются коды с тонкой структурой, известные под названием сверточных кодов. Эти коды можно генерировать с помощью цепей линейных регистров сдвига, выполняющих операцию свертки информационной последовательности. В конце 50-х годов для сверточных кодов были успешно разработаны алгоритмы последовательного декодирования. Интересно, что наиболее простой алгоритм декодирования - алгоритм Витерби - не был разработан для этих кодов до 1967 г. Применительно к сверточным кодам умеренной сложности алгоритм Витерби пользуется широкой популярностью, но для более мощных сверточных кодов он не практичен.

В 70-х годах эти два  направления исследований опять  стали переплетаться. Теорией сверточных кодов занялись алгебраисты, представившие ее в новом свете. В теории блоковых кодов за это время удалось приблизиться к кодам, обещанным Шенноном: были предложены две различные схемы кодирования (одна Юстесеном, а другая Гоппой), позволяющие строить семейства кодов, которые одновременно могут иметь очень большую длину блока и очень хорошие характеристики. Обе схемы, однако, имеют практические ограничения. Между тем к началу 80-х годов кодеры и декодеры начали появляться в конструкциях цифровых систем связи и цифровых систем памяти. 

ПРИЛОЖЕНИЯ

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

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

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

Связь важна также внутри одной  системы. В современных сложных  цифровых системах могут возникнуть большие потоки данных между подсистемами. Цифровые автопилоты, цифровые системы  управления процессами, цифровые переключательные системы и цифровые системы обработки  радарных сигналов - все это системы, содержащие большие массивы цифровых данных, которые должны быть распределены между многими взаимно связанными подсистемами. Эти данные должны быть переданы или по специально предназначенным  для этого линиям, или посредством  более сложных систем с шинами передачи данных и с разделением  по времени. В любом случае важную роль играют методы кодирования, контролирующего  ошибки, так как они позволяют  гарантировать соответствующие  характеристики.

ОБЩИЕ СВЕДЕНИЯ О КОДАХ И СИСТЕМАХ КОДИРОВАННОЙ СВЯЗИ

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

Если сообщения обладают внутренними корреляционными связями, т. е. если одно сообщение некоторым  образом зависит от другого, как  это обычно бывает при передаче текстов  на естественных языках, то помехоустойчивость любого кода может быть повышена за счет статистических связей между сообщениями. Если эти связи слабые, или неизвестны, или их нельзя использовать для повышения  помехоустойчивости, то в этом случае форма представления сообщения  должна быть избыточной; в частности, число символов в коде сообщения  увеличивают, а между кодовыми символами  вводят искусственные корреляционные связи. Поэтому в некоторых случаях  помехоустойчивые коды называют избыточными. Введение избыточности в код позволяет  помимо обнаружения и исправления  ошибок повысить энергетическую эффективность  линии связи, обузить частотный  спектр передаваемого сигнала, сократить  время вхождения в связь путем  повышения помехозащищенности тракта синхронизации, улучшить корреляционные свойства ансамбля сигналов, простыми средствами реализовать разнесенный  прием. Вид помехоустойчивого кода зависит от структуры системы  связи, обобщенная схема которой  приведена на рис. 1.1. Всюду рассматриваем  системы связи, передающие только дискретные сообщения. В современных системах передачи дискретных сообщений последние  поступают на вход системы, как правило, от нескольких источников. Даже если внешний источник один, сама система связи содержит источник сигналов служебной связи, телеуправления и телесигнализации (ТУ-ТС). Скорость поступления сообщений от разных источников может быть как одинаковой, так и различной синхронной с собственной тактовой частотой аппаратуры связи или асинхронной с ней. Блок уплотнения (БУ) объединяет сообщения, поступающие от разных источников, в единую последовательность, как правило, двоичных символов с тактовой частотой, соответствующей скорости передачи системы связи. 
 
  
Рис. 1 — Схема системы связи:

ИИ - источник информации; БУ - блок уплотнения сообщений;КДШ, КДВ - кодеры внешний, внутренний; ПРШ, ПРВ - перемежители внешний, внутренний; М - модулятор; ПД - передатчик; ЛС - линия связи; ПР - приемник; Д - демодулятор; АЦП - аналого-цифровой преобразователь; БДС, БПС, БЛС - блоки додетекторного, последетекторного, логического сложения; ДПШ, ДПВ - деперемежители внешний, внутренний; ДКШ, ДКВ - декодер внешний, внутренний; БР-блок разуплотнения сообщений; ПИ-получатель информации; КОС - канал обратной связи.

Если скорости поступления  сообщений от источников асинхронны по отношению к собственной тактовой частоте системы связи, БУ осуществляет асинхронный ввод сообщений. Для  того чтобы при временном уплотнении различить сообщения на стороне  приема, БУ формирует маркер, обозначающий место первого источника в  общем цифровом потоке. Маркер повторяется  периодически, образуя сигнал цикловой синхронизации. Кодер вводит избыточность в передаваемый поток двоичных символов, причем кодирование сообщений в  зависимости от требуемой степени  повышения помехоустойчивости может  выполняться поэтапно и соответственно этапам различными кодерами. Первый после БУ кодер называют внешним (КДШ), последний - внутренним (КДВ). Сформированный кодером поток символов поступает в перемежитель. Во многих случаях ошибка в одном символе кода влечет за собой ошибки и в других смежных с ним символах той же последовательности, вызывая появление пакета ошибок на входе декодера, исправляющего ошибки. Если код рассчитан на исправление m ошибок на интервале из n смежных символов, а пакет ошибок вызывает больше чем m ложных символов, ошибка декодером не будет исправлена. Перемежитель разносит (во времени) смежные символы исходной кодовой последовательности более чем на n символов. При деперемежении на стороне приема разнесенные символы вновь собирают вместе; одновременно ошибки в пакете будут разнесены деперемежителем во времени более чем на n символов, и соответствующий деперемежителю декодер такие разнесенные ошибки сможет исправить.

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

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

Сложение сигналов в разнесенных  ветвях на стороне приема может производиться  как на входе демодулятора (додетекторное сложение), так и на его выходе (последетекторное сложение). В частности, если сигналы в ветвях некогерентны, последетекторное сложение называют квадратичным. Сравнительно недавно в системах связи с кодированными сигналами стали применять логическое объединение ветвей разнесения, реализующее последетекторный автовыбор ветви с наименьшим числом ошибок. Демодулятор (Д) производит оптимальную обработку элемента сигнала, заканчивающуюся обычно интегрированием со сбросом интегратора в определенный тактовый момент времени. Тем самым демодулятор дискретизирует во времени смесь огибающей сигнала с шумом. Формирование тактовых импульсов осуществляют устройства тактовой синхронизации, входящие в состав демодулятора. Аналого-цифровой преобразователь (АЦП) на выходе демодулятора дискретизирует (квантует) смесь огибающей сигнала с шумом по уровню. При квантовании на два уровня декодируется двоичный сигнал. Максимальное число уровней квантования, как правило, не превышает 16. Обычно число уровней равно 2, 4, 8 или 16. Декодер, работающий с двоичным сигналом, называют жестким, с недвоичным - мягким. Для работы декодера необходимы специфические (групповые) тактовые импульсы, формируемые в тракте групповой синхронизации, входящем в состав декодера. Назначение декодера состоит в уменьшении числа ошибок в сообщениях, выдаваемых системой связи, путем использования избыточности, заложенной в символьный поток кодером. Часть системы связи, включающая линию (радио- или проводную), называется каналом. Часть системы от выхода модулятора до входа АЦП образует канал передачи-приема сигнала, непрерывного по уровню (но дискретного по времени). Часть системы от выхода модулятора до выхода АЦП образует канал с входным сигналом, непрерывным по уровню и времени, и с выходным дискретным сигналом. От входа модулятора до выхода АЦП имеем дискретный (по времени и уровню) канал. В двунаправленной системе связи обычно создают канал обратной связи, по которому осуществляют управление работой системы.