Материал: ОТС Лекции 1 и 2 часть

3. Формируем вектор ошибки V, т.е. кодовую комбинацию, которая содержит единицу на той позиции, где произошла ошибка. Формирование синдромов и векторов ошибок можно произвести заранее, искажая

последовательно символы в комбинации. Например, приняли: 0 0 0 0 0 0 0; (C1C2C3C4) = 0 0 0 0; V = (0 0 0 0 0 0 0) - ошибок нет;

Пусть приняли: 0000001 - это запрещенная комбинация ( ошибка в символе а7). Вычисляем синдром: (C1C2C3C4) = 0001. Вычисляем вектор ошибки: V=(0000001). Составим таблицу синдромов и соответствующих векторов одиночных ошибок .

36

.

5.3. Циклические коды Характерной особенностью циклических кодов является то, что циклическая

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

Алгоритм формирования циклического кода на примере кода (7, 4). Комбинации данного циклического кода состоят из 7 символов, из которых 4 символа информационные и 3 – проверочные.

1) Записываем возможные информационные комбинации из 4-х символов: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111.

2) Каждую комбинацию записываем в виде полинома. Например: 1 0 0 1 a(z) = z3 + 1

а3 а2 а1 а0 3) Выбираем из таблиц образующий полином, степень которого соответствует

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

В результате получим 16 комбинаций циклического кода (7,4): 0000000, 0001011, 0010110 и т.д…... Код состоит из совокупности двух подмножеств по 7 комбинаций, внутри которых циклические перестановки дают остальные и двух комбинаций 0000000 и 1111111. Минимальное кодовое расстояние равно 3, т.е. данный код исправляет все одиночные ошибки.

Алгоритм декодирования циклического кода на примере кода(7,4).

1) Принятая кодовая комбинация делится на образующий полином. Остаток от деления есть синдром, который указывает на позицию, где произошла ошибка. Т.к. синдром не зависит от передаваемой комбинации, а зависит только от позиции, в которой произошла ошибка, то синдромы можно вычислить заранее. Например, передавали комбинацию 0000000, под действием помехи она превратилась в 0100000, т.е. ошибка в 6-ом символе справа. Разделим 0100000

1000

1101

1010

1101

1110

1101

011

37

Остаток 011 и есть синдром, указывающий, что ошибка произошла в 6-ом символе справа.

2) В соответствии с синдромом формируется вектор ошибки, т.е. кодовая комбинация, которая содержит 1 в той позиции, где произошла ошибка. Для данного примера вектор ошибки V=0100000. Вектор ошибки суммируется по модулю 2 с принятой комбинацией:

0100000 0100000 = 0000000

Ошибка исправлена.

5.4.Сверточный код (решетчатый)

Свёрточный код относится к классу непрерывных кодов. Сверточный кодер (рис.5.3) после формирования выходной комбинации, соответствующей входному информационному символу, не переходит в исходное начальное состояние, а кодирует следующий информационный символ, начиная кодирование из того состояния, в котором он оказался после передачи предыдущего символа. Следовательно, между символами выходной кодированной последовательности существуют корреляционные связи, позволяющие повысить помехоустойчивость декодирования.

Кроме этого, сверточный кодер имеет не один, а n выходов, на каждом из которых формируется из одной и той же информационной последовательности своя собственная выходная последовательность в соответствии с порождающим полиномом, соответствующим данному выходу. Для рис. 5.3 n=2 и порождающие полиномы имеют вид: p1(z)= =(1+z2); p2(z)=(1+z+z2). Сначала передаются первые импульсы с каждого из n выходов, потом вторые и т.д. Очевидно, что скорость передачи падает в n раз.

Рис.5.3.

Сверточный код – частный случай решетчатых кодов. Решетчатая диаграмма на рис.5.4 для сверточного кода, формируемого кодером рис.5.3 - это один из способов задания сверточного кода. Каждое сечение соответствует внутреннему состоянию кодера; ребро соответствует передаваемому символу на входе: верхнее – 0; нижнее - 1. Около ребра написана комбинация из двух бит, которая появится на выходе, если на входе 1 или 0.

38

Рис.5.4.

Пусть на вход кодера рис.5.3 поступила комбинация 101. Ей соответствует полином a(z)=1+ z2. На первом выходе кодера получим b1(z)=a(z)*p1(z)= =(1+z2)*(1+ z2)=1+z4. Этот полином соответствует комбинации 10001.

На втором выходе кодера получим b2(z)=a(z)*p2(z)= (1+z2)*(1+z+z2) =1+ +z+z3+z4. Это соответствует комбинации 11011.Следует учесть, что сложение коэффициентов осуществляется по модулю 2, т.е.z+z=(1 1)z=0.

Совместим эти комбинации: сначала передается первый символ с первого выхода, потом первый символ со второго выхода, потом второй символ с первого выхода, потом второй символ со второго выхода и т.д. Получим 110100…… Аналогичный результат получим с помощью решетчатой диаграммы: при передаче 1 идем по нижнему ребру и в канал связи передается 11, далее передается 0, идем по верхнему ребру и в канал передается 01, далее передается 1, а в канал идет 00 и т.д.

Структурная схема декодера сверточного кода показана на рис.5.10. Декодирование сверточного кода осуществляется в соответствии со схемой рис.5.10. Пусть передавали 110100…., приняли 100100…Ошибка во 2-ом символе. Покажем, как декодер исправляет эту ошибку.

Рис.5.10.

Декодирование осуществляется поэтапно путем анализа очередных n бит (метрики ветвей). Для рассматриваемого кодера n=2. Приняли первые два бита 10. Кодовое расстояние между 10 и путем al, которому соответствует 00, равно

39

d=1(метрика ветви al). Кодовое расстояние между 10 и путем ab, которому соответствует 11, равно d=1 (метрика ветви ab). Сохраняем оба пути.

Приняли следующие два бита 01. Метрики путей, равные сумме метрик ветвей следующие : alm – 2; ali – 2; abf – 1; abc - 3.

Сохраняем пути (выжившие пути): alm, ali, abf. Приняли еще два бита 00. Метрики путей:

almn – 2; almj – 4; alig – 3; alid – 3; abfn – 3; abfj – 1.

Выбираем наивероятнейший путь abfj, метрика которого наименьшая – 1. Т.е. считаем, что передавалась комбинация 110100 – ошибка исправлена.

5.5. ПЕРЕМЕЖЕНИЕ Перемежение - эффективный способ борьбы с пакетами ошибок. В

реальных каналах связи принимаемый сигнал флуктуирует по амплитуде. Когда уровень сигнала падает практически до нуля, принимаемые кодовые комбинации содержат очень много ошибок, т.е. мы принимаем «пакет ошибок». Использование мощных кодов – неэффективно. На передаче осуществляется перемежение, т.е. сначала передаем первый символ первой комбинации a11, потом первый символ второй комбинации a21 и т.д. первый символ r –ой комбинации ar1. Далее передаются вторые символы и т.д.

Пусть пакет ошибок поразил группу символов a11, a21…. ar1.

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

6. ПРОПУСКНАЯ СПОСОБНОСТЬ КАНАЛА СВЯЗИ.

6.1. Условная энтропия. Взаимная информация.

В системе связи осуществляется передача информации от передатчика к приемнику. Если бы в канале связи отсутствовали помехи, то принятый сигнал ui(t) в разумно сконструированной системе связи однозначно соответствовал бы переданному vi(t). Следовательно, количество информации, содержащееся в сигнале ui(t), было бы передано по каналу связи. Количество информации, содержащееся, в среднем, в одном символе переданного сигнала, т.е. энтропия источника H (V) равнялась бы количеству информации, содержащемся, в среднем, в одном символе принятого сигнала H (U). Однако, в канале связи действуют помехи х(t) и поэтому на вход приемника поступает сумма сигнала и помехи, т.е. процесс z(t) = vi(t)+ х(t). Поэтому при передаче vi(t) с определенными вероятностями будут приняты или ui(t), соответствующий переданному vi(t), или uk(t), т.е. произойдет ошибка. Условная энтропия H(Z/U) характеризует мешающее влияние помехи, т.е. потери информации в канале связи из-за влияния помех.

Несмотря на влияние помех, процесс z(t) все-таки содержит информацию о сигнале u(t). Эта информация называется взаимной информацией I(U;Z),

содержащейся в процессе z(t) о процессе u(t). Взаимная информация равна

40