Вернер М. Основы кодирования

Подождите немного. Документ загружается.

8.3.

Примеры

\2i)

Информация

одного символа -

= 8 бит. (8.29)

Информационный

ноток -

/ =

Is = 80 кбит/cek. (8.30)

2. Пропускная способность канала равна

С = 10 кГц

•

Iog

(l + 10

) « 66 кбит/cek, (8.31)

таким образом, С < I. Безошибочная передача невозможна.

3. Минимально необходимое отношение сигнал/шум определяет-

ся

из (8.11)

10 кГц

•

Iog

(l + —) = 80 кбит/cek (8.32)

равно

~ = 255 «24,1 дБ. (8.33)

min

4. Минимально необходимое значение полосы пропускания вы-

числяется, исходя из (8.11)

Slog

(l + 10

) = 80 кбит/сек. (8.34)

Таким

образом, получаем

min

= 12 кГц. (8.35)

Пример:

Телефонный канал.

Стандартный аналоговый телефонный канал имеет полосу про-

пускания от 300 Гц до 3,4 кГц. Будем предполагать, что телефонный

узел связи обеспечивает на выходе заданное отношение сигнал/шум.

Каждый абонент связан с коммутатором парой проводов. Затуха-

ние

сигнала в полосе до 4 кГц составляет, приблизительно, 2 дБ/км.

Постройте график пропускной способности канала, как функцию

удаленности абонента от узла связи.

Решение.

Подставим в выражение для пропускной способности (8.11) зна-

чение отлошения сигнал/шум как функции расстояния /. Будем счи-

тать ширину полосы пропускания 4 кГц., тогда

С =

41og

icPMSNR-я/кт])

кбит

сек

. (

.зб)

124

Глава

Непрерывные

источники и каналы

Графики

зависимости пропускной способности от расстояния

приведены на рис. 8.9.

fkbit/s]

--VJ

SNR

[dBJ

"^60

1 '

^40

"*^30^j

^20

•^

*<—

r- ,

-—,.

—

/[km]

Рис.

8.9. Зависимость пропускной способности от дально-

сти

подключения.

Значение пропускной способности С как функции I, соответству-

ющее отношению сигнал/шум 60 дБ, падает почти линейно с ростом

О < / < 20 км с 80 кбит/сек до 26 кбит/сек. Подобным же образом

ведут

себя кривые, соответствующие меньшим начальным отноше-

ниям

сигнал/шум, однако, с уменьшением SNR, свойство линейности

утрачивается.

Замечание.

Статистика

показывает, что 99,5 %

абонентов,

под-

ключенных

центральному

узлу связи,

были

удалены

от

него

не

более

чем на 8 км. Фактически,

пропускная

способность

каналов

связи

существенно

выше,

чем

приведенная

примере.

Это

объяс-

няется

тем

фактом,

что

ширина

полосы

пропускания

пары

теле-

фонных

проводов

во

много

раз

выше

4 кГц.

Современные методы передачи информации по проводным линиям-

связи

(xDSL) позволяют реализовать скорость передачи данных до

нескольких Мбит/сек. Например, в стандарте ADSL, передача ин-

формации

осуществляется со скоростью выше 64 кбит/сек и исполь-

зуется полоса частот от 26... 138 кГц. При соединении абонентов

сеть со скоростью 6 Мбит/сек, полоса частот составляет 26... 1104

кГц.

Пример:

Телеграфия.

В телеграфии для передачи сообщений используются два симво-

ла - точка и тире. Отдельные символы разделены паузами. Будем

8.3.

Примеры 125,

считать, что длительность тире составляет 1 сек., а длительность

точки

и паузы - 1/3 сек.

Найдите

средний информационный ноток телеграфного источника.

Решение.

Из

таблицы 3.1

следует,

что отношение частот встречаемости то-

чек

и тире равно, приблизительно, 2:1 (с учетом вероятностей букв

алфавита в тексте). Значит, вероятности появления точки и тире

связаны

соотношением

"точка

2/тире

^точка + ^тире

(8.37)

Следовательно,

-Рточка

= 2/3 и Р

тире

= 1/3.

(8.38)

Энтропия

двоичного телеграфного источника

бит

точка

'•тиреlog

/тире

— 0,92.

(8.39)

Средняя

длительность одного символа, включая последующую пау-

зу, составляет

2/ос

очка

1/Згтире

Ч1ауза

(8.40)

2/3 • 1/3 сек + 1/3 сек + 1/3 сек = 8/9 сек.

Таким

образом, средний информационный поток равен

ВД

04 6ит

сек

(8.41)

ЧАСТЬ

ПОМЕХОУСТОЙЧИВОЕ

КОДИРОВАНИЕ

ГЛАВА I

ВВЕДЕНИЕ

Структурная

схема

процесса цифровой связи приведена на рис. 1.1.

Источник

выдает сообщение, которое в общем виде представляет со-

бой некоторый электрический сигнал. Аналоговый сигнал преобра-

зуется в цифровую форму,

удобную

для дальнейшей обработки.

Источник

Колер

I Кодер I

источника

I канала I

Получатель

Шум

Канал

Декодер I ' Декодер 1

источника

| канала I

Рис.

1.1. Модель передачи информации.

Заметим, что аналого - цифровое преобразование, как правило,

ограничивает полосу сигнала. Далее производится сжатие информа-

ции

(кодирование источника, см. часть I). Кодирование источника

удаляет

несущественную информацию и минимизирует, а иногда и

полностью устраняет избыточность сообщения. Таким образом, ко-

дирование источника снижает затраты на храпение и передачу ин-

формации.

Далее сообщение должно быть передано по зашумлен-

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

доведено до потребителя в неискаженном виде, перед передачей в ка-

нал производится помехоустойчивое кодирование информации (ко-

дирование канала). На приемном конце информация, поступающая

из

канала подвергается обратным преобразованиям. Декодер канала

исправляет ошибки в принятом слове, а декодер источника преобра-

зует

исправленное слово в форму,

удобную

потребителю.

В учебной

литературе

основное внимание уделяется не методам

устранения ошибок в канале, а оптимальным процедурам помехо-

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

Глава 1. Введение

живать

исправлять

эти

ошибки. При этом, говоря

кодах,

кон-

тролирующих ошибки, различают

две

стратегии

их

использования:

с непосредственным

исправлением

ошибок

за

счет

избыточности

(Forward Error Correction

FEC)

и с

обнаружением ошибок

с по-

следующими

запросами

на

повторную

передачу

ошибочно

принятой

информации

(Automatic Repeat Request

ARQ).

При

проектировании реальных систем связи, обычно, сочетают

выбор канала

выбором конкретных методов помехоустойчивого ко-

дирования. При этом, стремятся оптимизировать соотношение меж-

ду затратами

качеством передачи информации. Под качеством, как

правило, понимают среднюю

долю

ошибочных

бит (Bit

Error Rate

BER),

которая определяется,

как

средняя

вероятность

ошибки

од-

ного бита передаваемой информации.

Первым шагом разработки системы связи является выбор кон-

струкций передатчика

приемника,

также среды,

которой

будет

осуществляться передача данных.

точки зрения теории информа-

ции,

этим самым

мы

выбираем один

из

каналов, среди

всех

реально

существующих.

Опыт показывает,

что на

первом шаге разработчики

системы связи очень часто сталкиваются

с, так

называемым,

«эф-

фектом насыщения», который показан

на

рис.

1.2.

Используя стан-

дартную

технику передачи данных, можно получить некоторое

га-

рантированное качество связи, например,

для

мобильных каналов

BER

« 1(Г

, для

проводных каналов

BER та 10~

, для

волокон-

нооптических каналов

BER та

10~

При дальнейшем улучшении

качества связи средствами аналоговой техники, затраты

на

реализа-

цию резко возрастают.

Качество

цифровые

ситемы

' аналоговые

системы

Рис.

1.2.

Зависимость

между

затратами

качеством

в си-

стемах передачи информации.

Здесь

на

помощь приходит цифровая техника

помехоустой-

чивое кодирование. Путем применения оптимального кодирования,

можно обеспечить как

угодно

малую

BER (при условии R < С).

При

выборе методов кодирования и декодирования,

руководствуют-

ся

многими факторами, взаимосвязь которых показана на рис. 1.3.

В общую сложность входят.аппаратурные и программные затраты

на

реализацию кодера и декодера, цены специализированных микро-

схем

и микропроцессоров, стоимость памяти для хранения информа-

ции

и т.д. Интенсивность потока данных включает в себя передачу

полезной информации, проверочных разрядов, а также передачу за-

просов и повторений по этим запросам отдельных блоков сообщений.

Способность кода обнаруживать

исправлять ошибки

Интенсивность

потока

данных

Рис.

1.3. Взаимосвязь

между

параметрами кодовых кон-

струкций.

Методы помехоустойчивого кодирования довольно многообраз-

ны.

В этой книге мы ограничимся лишь описанием наиболее важных

классов блоковых и сверточных кодов. При этом, основное внимание

уделяется циклическим кодам из-за простоты их реализации. Цик-

лические коды

образуют

подмножество линейных блоковых кодов,

поэтому, наш вводный курс мы начнем с описания

структуры

и об-

щих свойств линейных блоковых кодов (подробнее см., например, [5]).

ГЛАВА 2

ЛИНЕЙНЫЕ

БЛОКОВЫЕ

КОДЫ

2.1.

Помехоустойчивое

кодирование

Реальные системы передачи данных не совершенны. Применяя ин-

формационную технику, мы должны учитывать возможность воз-

никновения

ошибок (вероятность ошибок) при передаче и хранении

информации.

Это в первую очередь относится к

• хранению информации на носителях с высокой плотностью за-

писи

(магнитные носители, CD — ROM, DVD).

• передаче данных при ограниченной мощности сигнала (спут-

никовая

и мобильная связь)

• передаче информации по сильно зашумлсниым каналам (мо-

бильная связь, высокоскоростные проводные линии связи)

• каналам связи с повышенными требованиями к надежности ин-

формации

(вычислительные сети, линии передачи со сжатием

данных)

Во

всех

вышеперечисленных

случаях

используются коды, контроли-

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

дого

конкретного канала позволяет выбрать наиболее эффективный

метод обнаружения и исправления ошибок.

Существуют

два взаимо-

дополняющих метода борьбы с помехами.

• Кодирование для исправления ошибок - приемник обнаружи-

вает

и исправляет ошибки;

• Кодирование для обнаружения ошибок приемник распознает

ошибки

и,

случае

необходимости, производит запрос на по-

вторную передачу ошибочного блока.

Последний метод предполагает наличие канала обратной связи

находит свое применение в каналах с достаточно малой вероят-

ностью ошибки в случае, если эту вероятность ошибки необходимо

2.1.

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

еще понизить. Такая ситуация часто возникает,

вычислительных

сетях и

интернете. Типичное значение вероятности ошибки на бит

без кодирования

вычислительных сетях составляет 10~

. Исполь-

зование простейших кодов

небольшой избыточностью позволяет

достигнуть вероятности 10~

ниже.

Замечание.

Требование

вероятности

ошибки

10~

не

является

чрезмерно

завышенным.

вычислительных

сетях,

например,

мо-

жет возникнуть

обрыв

связи

результате

повреждения

оптово-

локна

при

производстве

земляных

работ,

небрежного

подключения

кабеля

модему

т.д. Такой

обрыв

должен

быть

быстро

обна-

ружен

декодером,

который

случае

резкого

возрастания

частоты

переспросов

выдает

сигнал

обрыва

связи.

В последующих разделах идеи помехоустойчивого кодирования

будут

подробно объяснены на примерах линейных блоковых кодов.

Здесь

же

мы рассмотрим простейшую модель передачи данных

использованием помехоустойчивого кодирования (рис. 2.1).

Источник

Кодер

Сообщение

Кодовое слово

Кодер

Кодирование

канала

Получатель 4-

Декодер

Декодированное

сообщение

Принятое

слово

Рис.

2.1. Модель канала связи

кодированием.

Будем исходить из того, что при передаче информации исполь-

зуется блоковый код Хэмминга

, структура которого

будет

подробно

раскрыта в дальнейшем. Сейчас мы ограничимся его табличным опи-

санием.

Пусть кодер источника последовательно выдает

информаци-

онные

слова

фиксированной длины. Кодер канала заменяет каждое

информационное

слово

кодовым

словом

v в

соответствии с табл. 2.1.

Передатчик генерирует сигналы, соответствующие кодовому сло-

ву

v и

посылает

их в

канал. Приемник производит обратное пре-

Ричард

В.

Хэмминг:

1915/1998,

американский

математик.

132

Глава

Линейные

блоковые

коды

Таблица 2.1. Кодовая таблица (7,4)-кода Хэмминга.

Информационное

слово

0000

1000

0100

1100

0010

1010

0110

1110

Кодовое

слово

000 0000

ПО

1000

011

0100

101

1100

111

0010

001

1010

100

ОНО

010

1110

Информационное

слово

0001

1001

0101

1101

ООП

1011

0111

1111

Кодовое

слово

101

0001

011

1001

ПО

0101

000

1101

010

ООП

100

1011

001

0111

111

1111

образование,

в результате которого на декодер поступает двоичное

принятое

слово

г.

Декодер сравнивает принятое слово г со всеми кодовыми словами

табл. 2.1. Если слово г совпадает с одним из кодовых слов, то соот-

ветствующее информационное слово G выдается потребителю. Если

г отличается от всех кодовых слов, то в канале произошла обнару-

живаемая

ошибка.

Из

всего вышесказанного уже можно сделать два важных вывода:

•

Если в процессе передачи по зашумленному каналу кодовое

слово отобразится в

другое

кодовое слово, не совпадающее с

переданным,

то происходит необнаружимая ошибка. Назовем

ее остаточной

ошибкой

декодирования.

•

«Хорошие коды» обладают некоторой математической струк-

турой, которая позволяет эффективно распознать, а в некото-

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

информации

по каналу связи.

Из

структуры

кода Хэмминга

следует

одно интересное свойство, которое может

быть проверенно простым перебором:

Для любого произвольного вектора г

существует

ближайшее кодовое слово,

которое или полностью совпадает с г или отличается от него только в одном

двоичном разряде. Таким образом, если в векторе v при передаче по каналу

произошла только одна ошибка, она

всегда

может быть исправлена в процессе

декодирования.-

Прим.

перев.