Сверточное кодирование

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

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

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

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

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

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

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

В четвертом разделе была проведена экономическая оценка внедрения и разработки программного продукта. Рассчитаны затраты на создание данного ПО и определена его цена.

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

В шестом разделе коротко рассмотрены вопросы касающиеся гражданской обороны.

Программный эмулятор предназначен для использования в учебном процессе. Использование данной программы позволяет существенно ускорить и упростить процесс расчета.

сверточный кодирование программный

1. Постановка задачи

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

Для достижения цели работы необходимо решить следующие задачи:

— Исследовать возможные виды помехоустойчивых кодов.

— Классифицировать сверточный код в общей системе помехоустойчивого кодирования

— Ознакомиться с методом сверточного кодирования

— Ознакомиться с методом сверточного декодирования

— Разработать алгоритм программы, осуществляющей сверточное кодирование/декодирование и имитацию канала связи.

— В соответствии со спроектированным алгоритмом, предварительно выбрав язык программирования и среду разработки, создать программный модуль.

Входными данными в данной работе являются:

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

— Эффективная скорость передачи кода R=½

— Алгоритм декодирования Витерби

— Графическое отображение решетчатой диаграммы при декодировании

— Локальная версия программы, которая устанавливается на конкретный компьютер, авторизуется и работает только на нем

— Программа предназначена для работы в среде ОС Windows. К аппаратным средствам выдвигаются те же требования, которые необходимы операционной системе для стабильной работы: 1Гб оперативной памяти и более, процессор с частотой 1 ГГц, порядка 5 Мб дискового пространства, видеокарта с памятью 32 Мб и более.

2. Предметная область

2.1 Актуальность использования сверточных кодов

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

Системы сотовой подвижной связи (ССПС) впервые стали эксплуатироваться в конце 70-х — начале 80-х годов. Сотовый принцип топологии сети с повторным использованием частот в сотах во многом решил проблему дефицита частотного ресурса и в настоящее время является основным в создаваемых системах подвижной связи общего пользования. Стандартизация в области ССПС привела к тому, что на смену девяти отдельным аналоговым стандартам сотовой связи первого поколения пришли три цифровых стандарта второго поколения (GSM, D-AMPS, JDC), один из них — GSM признан «глобальным». В связи с широким распространением этого стандарта во всем мире, GSM стали расшифровывать как Global System for Mobile Communications (глобальная система для мобильной связи).

Каналы связи в стандарте GSM разделяются на физические и логические. Физический канал образуется путем комбинирования временного (ВРК) и частотного (ЧРК) разделения сигналов.

До формирования физического канала сообщения данные, представленные в цифровом виде, группируются и объединяются в логические каналы двух типов:

— канал связи — для передачи кодированной речи и данных;

— канал управления — для передачи сигналов управления и синхронизации.

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

— блочное кодирование — для быстрого обнаружения ошибок при приеме;

— сверточное кодирование — для исправления одиночных ошибок;

— перемежение — для преобразования пакета ошибок в одиночные ошибки.

В цифровых ССПС кодируются все передаваемые по радиоканалу сигналы. В аналоговых ССПС кодируют цифровые сигналы управления.

При кодировании преследуют различные цели. Самый низкий уровень имеет выявление (обнаружение) ошибок в полностью принятом сигнале. По сравнению с ним более высоким уровнем обладает обнаружение ошибок в отдельных сегментах сигнала, которое может быть выполнено с помощью простых блоковых кодов, например, с проверкой на четность. В современных системах используют коды с исправлением ошибок. Это могут быть блоковые коды (каналы сигнализации в NMT-450, DECT) и сверточные коды (GSM, системы с кодовым разделением — CDMA). Выбор кода определяет большое число факторов: характеристики каналов, скорость передачи, вид модуляции и т. п. Важное значение приобретает элементно-технологическая база. Применение быстродействующих процессорных СБИС открыло путь к использованию мощных сверточных кодов при обработке сигналов в реальном времени. Сверточные коды хорошо исправляют случайные одиночные ошибки, но дают плохие результаты при пакетах ошибок. Поэтому сверточное кодирование и совмещают с перемежением (перетасовкой) информационных символов, которое обеспечивает преобразование пакетов ошибок в одиночные.

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

В различных логических каналах используются различные сверточные коды, поскольку скорости передачи и требования по защите от ошибок также различны. Для упрощения процедур кодирования и декодирования при формировании кодов используются только несколько полиномов. Это позволяет использовать в стандарте GSM сверточный код с одной скоростью R = ½. В ряде режимов для выравнивания скорости в речевом канале до R = ½ применяют прореживание, т. е. периодический пропуск (перфорацию) кодированных символов. Поскольку сложность декодирования по наиболее выгодному, с точки зрения реализации, алгоритму Витерби возрастает экспоненциально с увеличением длины кодового ограничения l, то типовые значения ДКО малы и лежат в интервале l = 3 — 10.

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

Для существенного улучшения помехоустойчивости при использовании сверточных кодов необходимо увеличивать скорость передачи символов, а следовательно, и ширину полосы, например, в 2 раза при относительной скорости передачи кода ½ или в 4/3 раза при относительной скорости ¾. Таким образом, применение сверточных кодов оказывается особенно выгодным в спутниковых системах связи, энергетический потенциал которых ограничивается мощностью бортового ретранслятора, т. е. в каналах, где определяющим фактором является ограничение мощности, а не полосы частот. В системах с ограниченной энергетикой кодирование позволяет уменьшить необходимое отношение сигнал — шум, оптимальным образом распределить мощность ретранслятора между каналами и увеличить число каналов.

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

Таким образом, сверточные коды применяются в широком спектре современных систем связи.

2.2 Передача информации по каналам связи

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

Для анализа информационных процессов в канале связи можно использовать его обобщенную схему, приведенную на рис. 2.1.

Рисунок 2.1 — Обобщенная схема канала связи На рисунке 2.1 приняты следующие обозначения: X, Y, Z, W — сигналы, сообщения; f — помеха; ЛС — линия связи; ИИ, ПИ — источник и приемник информации; П — преобразователи (кодирование, модуляция, декодирование, демодуляция).

Существуют различные типы каналов, которые можно классифицировать по различным признакам:

1. По типу линий связи: проводные; кабельные; оптико-волоконные;

2. линии электропередачи; радиоканалы и т. д.

3. По характеру сигналов: непрерывные; дискретные; дискретно-непрерывные (сигналы на входе системы дискретные, а на выходе непрерывные, и наоборот).

4. По помехозащищенности: каналы без помех; с помехами.

Каналы связи характеризуются:

1. Емкость канала определяется как произведение времени использования канала T_к, ширины спектра частот, пропускаемых каналом F_к и динамического диапазона D_к., который характеризует способность канала передавать различные уровни сигналов

V_к = T_к F_к D_к. (1)

Условие согласования сигнала с каналом:

V_c V_k; T_c T_k; F_c F_k; V_c V_k; D_c D_k.

2. Скорость передачи информации — среднее количество информации, передаваемое в единицу времени.

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

4. Избыточность — обеспечивает достоверность передаваемой информации (R = 01).

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

Проводные:

1. Проводные — витая пара (что частично подавляет электромагнитное излучение других источников). Скорость передачи до 1 Мбит/с. Используется в телефонных сетях и для передачи данных.

2. Коаксиальный кабель. Скорость передачи 10−100 Мбит/с — используется в локальных сетях, кабельном телевидении и т. д.

3. Оптико-волоконная. Скорость передачи 1 Гбит/с.

4. В средах 1−3 затухание в дБ линейно зависит от расстояния, т. е. мощность падает по экспоненте. Поэтому через определенное расстояние необходимо ставить регенераторы (усилители).

Радиолинии:

1. Радиоканал. Скорость передачи 100−400 Кбит/с. Использует радиочастоты до 1000 МГц. До 30 МГц за счет отражения от ионосферы возможно распространение электромагнитных волн за пределы прямой видимости. Но этот диапазон сильно зашумлен (например, любительской радиосвязью). От 30 до 1000 МГц — ионосфера прозрачна и необходима прямая видимость. Антенны устанавливаются на высоте (иногда устанавливаются регенераторы). Используются в радио и телевидении.

2. Микроволновые линии. Скорости передачи до 1 Гбит/с. Используют радиочастоты выше 1000 МГц. При этом необходима прямая видимость и остронаправленные параболические антенны. Расстояние между регенераторами 10−200 км. Используются для телефонной связи, телевидения и передачи данных.

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

2.3 Помехоустойчивые коды

Обнаружение ошибок в технике связи — действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) — процедура восстановления информации после чтения её из устройства хранения или канала связи.

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

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

Помеха — белый шум с Гауссовским законом распределения. В природе и технике «чисто» белый шум (то есть белый шум, имеющий одинаковую спектральную мощность на всех частотах) не встречается (ввиду того, что такой сигнал имел бы бесконечную мощность), однако под категорию белых шумов попадают любые шумы, спектральная плотность которых одинакова (или слабо отличается) в рассматриваемом диапазоне частот. Иногда ошибочно предполагается, что гауссовский шум (то есть шум с гауссовским распределением по амплитуде — нормальное распределение) обязательно является белым шумом. Однако эти понятия неэквивалентны. Гауссовский шум предполагает распределение значений сигнала в виде нормального распределения, тогда как термин «белый» имеет отношение к корреляции сигнала в два различных момента времени (эта корреляция не зависит от распределения амплитуды шума).

Нормальное распределение, также называемое гауссовским распределением или распределением Гаусса — распределение вероятностей, которое играет важнейшую роль во многих областях знаний. Физическая величина подчиняется нормальному распределению, когда она подвержена влиянию огромного числа случайных помех. Ясно, что такая ситуация крайне распространена, поэтому можно сказать, что из всех распределений в природе чаще всего встречается именно нормальное распределение — отсюда и произошло одно из его названий. Нормальное распределение зависит от двух параметров — смещения и масштаба, то есть является с математической точки зрения не одним распределением, а целым их семейством. Значения параметров соответствуют значениям среднего (математического ожидания) и разброса (стандартного отклонения).

2.3.1 Способы борьбы с ошибками

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

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

— обнаружение ошибок в блоках данных и автоматический запрос повторной передачи повреждённых блоков — этот подход применяется в основном на канальном и транспортном уровнях;

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

— исправление ошибок (forward error correction) применяется на физическом уровне.

2.3.2 Коды обнаружения и исправления ошибок

Корректирующие коды — коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием помех, а также при её хранении.

Для этого при записи (передаче) в полезные данные добавляют специальным образом структурированную избыточную информацию (контрольное число), а при чтении (приёме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.

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

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

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

2.4 Классификация конечных абстрактных автоматов

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

2.4.1 Автомат Мили

Автомат Мили (англ. Mealy machine) — конечный автомат, выходная последовательность которого (в отличие от автомата Мура) зависит от состояния и входной последовательности.

Математическая модель автомата состоит из совокупность пяти объектов:

где:

и — конечные непустые множества, а и — отображения вида:

и

со связью элементов множеств S, X и Y в абстрактном времени T = {0, 1, 2, …} уравнениями:

(Отображения и получили названия, соответственно функции переходов и функции выходов автомата A).

Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y (t) обнаруживается только при наличии символа во входном канале x (t).

Рисунок 2.2 — Функциональная схема автомата Мили

2.4.2 Автомат Мура

Зависимость выходного сигнала только от состояния представлена в автоматах типа Мура (англ. Moore machine). В автомате Мура функция выходов определяет значение выходного символа только по одному аргументу — состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе.

Конечным детерминированным автоматом типа Мура называется совокупность пяти объектов:

где, и — соответствуют определению автомата типа Мили, а является отображением вида: .

с зависимостью состояний и выходных сигналов во времени уравнением:

Особенностью автомата Мура является то, что символ y (t) в выходном канале существует все время, пока автомат находится в состоянии s (t).

Для любого автомата Мура существует автомат Мили, реализующий туже самую функцию. И наоборот: для любого автомата Мили существует соответствующий автомат Мура.

Рисунок 2.3 — Функциональная схема автомата Мура

2.5 Сверточное кодирование

Типичная функциональная схема системы цифровой связи использующая сверточное кодирование/декодирование и модуляцию/демодуляцию, показана на рисунке 2.4. Исходное сообщение на входе обозначается последовательностью где , — двоичный знак (бит), a i — индекс времени. Если быть точным, то элементы m следовало бы дополнять индексом члена класса (например, для бинарного кода, 1 или 0) и индексом времени. В дальнейшем для простоты будем использовать только индекс, обозначающий время (или расположение элемента внутри последовательности). Будем предполагать, что все, равновероятно равны единице или нулю и независимы между собой. Будучи независимой, последовательность битов нуждается в некоторой избыточности, т. е. знание о бите, не дает никакой информации о бите, (при). Кодер преобразует каждую последовательность m в уникальную последовательность кодовых слов. Даже несмотря на то что последовательность m однозначно определяет последовательность U, ключевой особенностью сверточных кодов является то, что данный k-кортеж внутри m не однозначно определяет связанные с ним n-кортежи внутри U, поскольку кодирование каждого из k-кортежей является функцией не только k-кортежей, но и предыдущих К-1 k— кортежей. Последовательность U можно разделить на последовательность кодовых слов:. Каждое кодовое слово U, состоит из двоичных кодовых символов, часто называемых канальными символами, канальными битами, или битами кода; в отличие от битов входного сообщения, кодовые символы не являются независимыми.

В типичных системах связи последовательность кодовых слов U модулируется сигналом. В ходе передачи сигнал искажается шумом, в результате чего, как показано на рисунке 2.4, получается сигнал и демодулированная последовательность Задача декодера состоит в получении оценки исходной последовательности сообщения с помощью полученной последовательности Z и априорных знаний о процедуре кодирования.

Рисунок 2.4 — Кодирование/декодирование и модуляция/демодуляция в канале связи Обычный сверточный кодер, показанный на рисунке 2.5, реализуется с kK-разрядным регистром сдвига и n сумматорами по модулю 2, где K — длина кодового ограничения. Длина кодового ограничения — это количество k-битовых сдвигов, после которых один информационный бит может повлиять на выходной сигнал кодера. В каждый момент времени на место первых k разрядов регистра перемещаются k новых бит; все биты в регистре смещаются на k разрядов вправо, и выходные данные n сумматоров последовательно дискретизируются, давая, в результате, биты кода. Затем эти симво лы кода используются модулятором для формирования сигналов, которые будут пере даны по каналу. Поскольку для каждой входной группы из к бит сообщения имеется n бит кода, степень кодирования равна k/n бит сообщения на бит кода, где k < n.

Рисунок 2.5 — Сверточный кодер с длиной кодового ограничения K и степенью кодирования k/n

Рассмотрим только наиболее часто используемые двоичные сверточные кодеры, для которых k — 1, т. е. те кодирующие устройства, в которых биты сооб щения сдвигаются по одному биту за раз, хотя обобщение на алфавиты более высоких порядков не вызывает никаких затруднений. Для кодера с k = 1, за i-й момент времени бит сообщения, будет перемещен на место первого разряда регистра сдвига; все предыдущие биты в регистре будут смещены на один разряд вправо, а выход ной сигнал n сумматоров будет последовательно оцифрован и передан. Поскольку для каждого бита сообщения имеется n бит кода, степень кодирования равна 1/n. Имеющиеся в момент времени, n кодовых символов составляют i-е кодовое слово ветви, где (j — 1, 2, …, n) — это j-й кодовый символ, принадлежащий i-му кодовому слову ветви. Отметим, что для кодера со степенью кодирования 1/n, kK-разрядный регистр сдвига для простоты можно называть K-разрядным регистром, а длину кодового ограничения K, которая выражается в единицах разрядов k-кортежей, можно именовать длиной кодового ограничения в битах.

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

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

2.5.2 Представление связи

При рассмотрении сверточных кодеров в качестве модели будем использовать сверточный кодер, показанный на рисунке 2.6. На этом рисунке изображен сверточный кодер (2, 1) с длиной кодового ограничения K = 3. В нем имеется n = 2 сумматора по модулю 2; следовательно, степень кодирования кода k/n равна ½. При каждом поступлении бит помещается в крайний левый разряд, а биты регистра смещаются на одну позицию вправо. Затем коммутатор на выходе дискретизирует выходы всех сумматоров по модулю 2 (т.е. сначала верхний сумматор, затем нижний), в результате чего формируются пары кодовых символов, образующих кодовое слово, связанное с только что поступившим битом. Это выполняется для каждого входного бита. Выбор связи между сумматорами и разрядами регистра влияет на характеристики кода. Всякое изменение в выборе связей приводит в результате к различным кодам.

В отличие от блочных кодов, имеющих фиксированную длину слова n, в сверточных кодах нет определенного размера блока. Однако с помощью периодического отбрасывания сверточным кодам часто принудительно придают блочную структуру. Это требует некоторого количества нулевых разрядов, присоединенных к концу входной последовательности данных, которые служат для очистки (или «промывки») регистра сдвига от бит данных. Поскольку добавленные нули не несут дополнительной информации, эффективная степень кодирования будет ниже k/n. Чтобы степень кодирования оставалась близкой к k/n, период отбрасывания чаще всего делают настолько большим, насколько это возможно.

Рисунок 2.6 — Сверточный кодер (степень кодирования ½, K — 3)

Один из способов реализации кодера заключается в определении n векторов связи, по одному на каждый из n сумматоров по модулю 2. Каждый вектор имеет размерность K и описывает связь регистра сдвига кодера с соответствующим сумматором по модулю 2. Единица на i-Й позиции вектора указывает на то, что соответствующий разряд в регистре сдвига связан с сумматором по модулю 2, а нуль в данной позиции указывает, что связи между разрядом и сумматором по модулю 2 не существует. Для кодера на рисунке 2.6 можно записать вектор связи для верхних связей, a — для нижних.

Предположим теперь, что вектор сообщения m = 1 0 1 закодирован с использованием сверточного кода и кодера, показанного на рисунке 2.6. Введены три бита сообщения, по одному в момент времени, и, как показано на рисунке 2.7. Затем для очистки регистра в моменты времени t₄ и t₅ введены (К — 1) = 2 нуля, что в результате приводит к смещению конечного участка на всю длину регистра. Последовательность на выходе выглядит следующим образом: 1 1 1 0 0 0 1 0 1 1, где крайний левый символ представляет первую передачу. Для декодирования сообщения нужна полная последовательность на выходе (включающая кодовые символы). Для удаления со общения из кодера требуется на единицу меньше нулей, чем имеется разрядов в регистре, или К — 1 очищенных бит. В момент времени t₆ показан нулевой выход, это должно дать читателю возможность убедиться в том, что в момент времени t₅ регистр устанавливается в исходное состояние. Таким образом, в момент времени t₆ уже можно передавать новое сообщение.

2.5.3 Реакция кодера на импульсное возмущение

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

Рисунок 2.7 — Сверточное кодирование последовательности сообщения со степенью кодирования ½ кодером с К = 3.

Рис.

Последовательность на выходе при единице на входе называется откликом кодера на импульсное возмущение, или его импульсной характеристикой. Для входной последовательности m = 1 0 1 данные на выходе могут быть найдены путем суперпозиции или линейного сложения смещенных во времени входных «импульсов» .

Рис.

Следует отметить, что эти данные на выходе такие же, как и на рис. 2.7, что указывает на линейность сверточных кодов — точно так же как и в блочных кодах. Название сверточный кодер (convolutional encoder) возникло именно вследствие этого свойства генерации данных на выходе с помощью линейного сложения (или свертки) смещенных во времени импульсов последовательности на входе с импульс ной характеристикой кодера. Такие устройства часто описываются с помощью матричного генератора бесконечного порядка.

Отметим, что в рассмотренном выше примере входной последовательности из 3 бит и последовательности на выходе из 10 бит эффективная степень кодирования составляет k/n = 3/10, что значительно меньше величины ½, которую можно было бы ожидать, зная, что каждый бит данных на входе порождает пару канальных битов на выходе. Причина этого заключается в том, что финальные биты данных нужно про вести через кодер. Все канальные биты на выходе требуются в процессе декодирования. Если бы сообщение было длиннее, скажем 300 бит, последовательность кодовых слов на выходе содержала бы 640 бит и значение для степени кодирования кода 300/640 было бы значительно ближе к ½.

2.5.4 Полиномиальное представление

Иногда связи кодера описываются с помощью полиномиального генератора для описания реализации обратной связи регистра сдвига циклических кодов. Сверточный кодер можно представить в виде набора из n полиномиальных генераторов, по одному для каждого из n сумматоров по модулю 2. Каждый полином имеет порядок K — 1 или меньше и описывает связь кодирующего регистра сдвига с соответствующим сумматором по модулю 2, почти так же как и вектор связи. Коэффициенты возле каждого слагаемого поли нома порядка (К — 1) равны либо 1, либо 0, в зависимости от того, имеется ли связь между регистром сдвига и сумматором по модулю 2. Для кодера на рис 2.6 можно записать полиномиальный генератор для верхних связей и — для нижних.

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

чередуется с

Прежде всего, выразим вектор сообщения m = 1 0 1 в виде полинома, т. е.. Для очистки регистра мы снова будем предполагать использование нулей, следующих за битами сообщения. Тогда выходящий полином U(X), или выходящая последовательность U кодера (рис. 2.6) для входного сообщения m может быть найдена следующим образом:

Рис.

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

2.5.5 Представление состояния и диаграмма состояний

Сверточный кодер принадлежит классу устройств, известных как конечный авто мат. Для сверточного кода со степенью кодирования 1/n состояние представлено содержимым K — 1 крайних правых разрядов (рис. 2.7). Знание состояния плюс знание следующих данных на входе является необходимым и достаточным условием для определения данных на выходе. Итак, пусть состояние кодера в момент времени, определяется как. i-я ветвь кодовых слов U, полностью определяется состоянием X, и введенными в настоящее время битами; таким образом, состояние X, описывает предысторию кодера для определения данных на его выходе. Состояния кодера считаются Марковскими в том смысле, что вероятность нахождения в состоянии, определяемая всеми предыдущими состояниями, зависит только от самого последнего состояния, т. е. она равна .

Одним из способов представления простых кодирующих устройств является диаграмма состояния (state diagram); такое представление кодера, изображенного на рис. 2.6, показано на рис. 2.8. Состояния, показанные в рамках диаграммы, представляют собой возможное содержимое К — 1 крайних правых разрядов регистра, а пути между состояниями — кодовые слова ветвей на выходе, являющиеся результатом переходов между такими состояниями. Состояния регистра выбраны следующими: а = 00, b = 10, с = 01 и d = 11; диаграмма, показанная на рис. 2.8, иллюстрирует все возможные смены состояний для кодера, показанного на рис. 2.6. Существует всего два исходящих из каждого состояния перехода, соответствующие двум возможным входным битам. Далее для каждого пути между со стояниями записано кодовое слово на выходе, связанное с переходами между со стояниями. При изображении путей, сплошной линией принято обозначать путь, связанный с нулевым входным битом, а пунктирной линией — путь, связанный с единичным входным битом. Отметим, что за один переход невозможно перейти из данного состояния в любое произвольное. Так как за единицу времени перемещается только один бит, существует только два возможных перехода между состояниями, в которые регистр может переходить за время прохождения каждого бита.

Рисунок 2.8 — Диаграмма состояний кодера (степень кодирования ½, К= 3)

2.5.6 Древовидные диаграммы

Несмотря на то, что диаграммы состояний полностью описывают кодер, по сути, их нельзя использовать для легкого отслеживания переходов кодера в зависимости от времени, поскольку диаграмма не представляет динамики изменений. Древовидная диаграмма (tree diagram) прибавляет к диаграмме состояния временное измерение.

Древовидная диаграмма сверточного кодера, показанного на рис. 2.6, изображена на рис. 2.9. В каждый последующий момент прохождения входного бита процедура кодирования может быть описана с помощью перемещения по диаграмме слева направо, причем каждая ветвь дерева описывает кодовое слово на выходе. Правило ветвления для нахождения последовательности кодовых слов следующее: если входным битом является нуль, то он связывается со словом, которое находится путем перемещения в следующую (по направлению вверх) правую ветвь; если входной бит — это единица, то кодовое слово находится путем перемещения в следующую (по направлению вниз) правую ветвь.

Предполагается, что первоначально кодер содержал одни нули. Диаграмма показывает, что если первым входным битом был нуль, то кодовым словом ветви на выходе будет 00, а если первым входным битом была единица, то кодовым словом на выходе будет 11. Аналогично, если первым входным битом была единица, а вторым — нуль, на выходе вторым словом ветви будет 10. Если первым входным битом была единица и вторым входным битом была единица, вторым кодовым словом на выходе будет 01. Следуя этой процедуре, видим, что входная последовательность 110 11 представляется жирной линией, нарисованной на древовидной диаграмме (рис. 2.9). Этот путь соответствует выходной последовательности кодовых слов 1 1 0 1 0 1 0 0 0 1.

Добавленное измерение времени в древовидной диаграмме (по сравнению с диаграммой состояния) допускает динамическое описание кодера как функции конкретной входной последовательности. Однако при попытке описания с помощью древовидной диаграммы последовательности произвольной длины возникает проблема: число ответвлений растет как 2^L, где L — это количество кодовых слов ветвей в последовательности.

2.5.7 Решетчатая диаграмма

Исследование древовидной диаграммы на рис. 2.9 показывает, что в этом приме ре после третьего ветвления в момент времени t₄ структура повторяется (в общем случае древовидная структура повторяется после К ответвлений, где К — длина кодового ограничения). Пометим каждый узел в дереве (рис. 2.9), ставя в соответствие четыре возможных состояния в регистре сдвига: а = 00, b = 10, с = 01 и d = 11. Пер вое ветвление древовидной структуры в момент времени дает пару узлов, помеченных как, а и b. При каждом последующем ветвлении количество узлов удваивается. Второе ветвление в момент времени t₂ дает в результате четыре узла, помеченных как а, b, с и d. После третьего ветвления всего имеется восемь узлов: два — а, два — b, два — с и два — d.

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

Следовательно, входные последовательности 1 0 0 х у… и 0 0 0 х у…, где крайний левый бит является самым ранним, после (К = 3)-го ветвления генерируют одинаковые кодовые слова ветвей.

Это означает, что любые состояния, имеющие одинаковую метку в один и тот же момент можно соединить, поскольку все последующие пути будут неразличимы. Если мы проделаем это для древовидной структуры, показанной на рис. 2.9, получим иную диаграмму, называемую решетчатой.

Рисунок 2.9 — Древовидное представление кодера (степень кодирования ½, К= 3)

Решетчатая диаграмма, которая использует повторяющуюся структуру, дает более удобное описание кодера, по сравнению с древовидной диаграммой. Решетчатая диаграмма для сверточного кодера, изображенного на рис. 2.6, показана на рис. 2.10.

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

Рисунок 2.10 — Решетчатая диаграмма кодера (степень кодирования ½, К= 3)

Узлы решетки представляют состояния кодера; первый ряд узлов соответствует состоянию a = 00, второй и последующие — состояниям b = 10, с = 01 и d — 11. В каждый момент времени для представления 2^К-1 возможных со стояний кодера решетка требует 2^К-1 узлов. В нашем примере после достижения глубины решетки, равной трем (в момент времени t₄), замечаем, что решетка имеет фиксированную периодическую структуру. В общем случае фиксированная структура реализуется после достижения глубины К. Следовательно, с этого момента в каждое состояние можно войти из любого из двух предыдущих состояний. Также из каждого состояния можно перейти в одно из двух состояний. Из двух исходящих ветвей одна соответствует нулевому входному биту, а другая — единичному входному биту. На рис. 2.10 кодовые слова на выходе соответствуют переходам между состояниями, показанными как метки на ветвях решетки.

Один столбец временного интервала сформировавшейся решетчатой структуры кодирования полностью определяет код. Несколько столбцов показаны исключительно для визуализации последовательности кодовых символов как функции времени. Со стояние сверточного кодера представлено содержанием крайних правых K — 1 разрядов в регистре кодера. Некоторые авторы описывают состояние с помощью крайних левых K -1 разрядов. Какое описание правильно? Они оба верны. Каждый переход имеет начальное и конечное состояние. Крайние правые K — 1 разрядов описывают начальное состояние для текущих входных данных, которые находятся в крайнем левом разряде (степень кодирования предполагается равной 1/n). Крайние левые К — 1 разрядов являются конечным состоянием для такого перехода. Последовательность кодовых символов характеризуется N ветвями (что представляет N бит данных), занимающими N интервалов времени. Она связана с конкретным состоянием в каждый из N +1 интервалов времени (от начала до конца). Таким образом, мы запускаем биты в моменты времени t₁, t₂, …, t_N и интересуемся метрикой состояния в моменты времени t₁, t₂, …, t_N+1. Здесь использовано следующее условие: текущий бит располагается в крайнем левом разряде, а крайние правые K — 1 разрядов стартуют из состояния со всеми нулями. Этот момент времени обозначим как начальное время, t₁. Время завершения последнего перехода обозначим как время прекращения работы, t_N+1.

2.6 Декодирование по методу максимального правдоподобия

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

(2.1)

по всем .

Принцип максимального правдоподобия, определяемый уравнением (2.1), является фундаментальным достижением теории принятия решений [1]; это формализация способа принятия решений, основанного на «здравом смысле», когда имеются статистические данные о вероятностях. При рассмотрении двоичной демодуляции предполагается передача только двух равновероятных сигналов и. Следовательно, принятие двоичного решения на основе принципа максимального правдоподобия, касающееся данного полученного сигнала, означает, что в качестве переданного сигнала выбирается, если В противном случае считается, что передан был сигнал. Параметр z представляет со бой величину z (T), значение принятого сигнала до детектирования в конце каждого периода передачи символа t=T. Однако при использовании принципа максимального правдоподобия в задаче сверточного декодирования, в сверточном коде обнаруживается наличие памяти (полученная последовательность является суперпозицией текущих и предыдущих двоичных разрядов). Таким образом, применение принципа максимального правдоподобия при декодировании бит данных, закодированных сверточным кодом, осуществляется в контексте выбора наиболее вероятной последовательности, как показано в уравнении (2.1). Обычно имеется множество возможных переданных последовательностей кодовых слов. Что касается двоичного кода, то последовательность из L кодовых слов является членом набора из 2^L возможных последовательностей. Следователь но, в контексте максимального правдоподобия можно сказать, что в качестве переданной последовательности декодер выбирает, если правдоподобие больше правдоподобия всех остальных возможно переданных последовательностей. Такой оптимальный декодер, минимизирующий вероятность ошибки (когда все переданные последовательности равновероятны), известен как декодер, работающий по принципу максимального правдоподобия (maximum likelihood detector). Функция правдоподобия за дается или вычисляется, исходя из спецификации канала. Предположим, что мы имеем дело с аддитивным белым гауссовым шумом с нулевым средним, следовательно, каналом без памяти, т. е. шум влияет на каждый символ кода независимо от остальных символов. При степени кодирования сверточного кода, равной 1/n, правдоподобие можно выразить следующим образом:

(2.2)

где — i-я ветвь принятой последовательности Z

— это ветвь отдельной последовательности кодовых слов

— это j-й кодовый символ

— это j-й кодовый символ, а каждая ветвь состоит из n кодовых символов.

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

было максимальным.(2.3)

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

(2.4)

Теперь задача декодирования заключается в выборе пути вдоль дерева на рис. 2.9 или решетки на рис. 2.10 таким образом, чтобы было максимальным. При де кодировании сверточных кодов можно использовать как древовидную, так и решетчатую структуру. При древовидном представлении кода игнорируется то, что пути снова объединяются. Для двоичного кода количество возможных последовательностей, состоящих из L кодовых слов, равно 2^L. Поэтому декодирование полученных последовательностей, основанное на принципе максимального правдоподобия с использованием древовидной диаграммы, требует метода «грубой силы» или исчерпывающего сопоставления 2^L накопленных логарифмических метрик правдоподобия, описывающих все варианты возможных последовательностей кодовых слов.

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

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

2.6.1 Алгоритм сверточного декодирования Витерби

В 1967 году Витерби разработал и проанализировал алгоритм [3], в котором, по сути, реализуется декодирование, основанное на принципе максимального правдоподобия; однако в нем уменьшается вычислительная нагрузка за счет использования особенностей структуры конкретной решетки кода. Преимущество декодирования Витерби, по сравнению с декодированием по методу «грубой силы», заключается в том, что сложность декодера Витерби не является функцией количества символов в последовательности кодовых слов. Алгоритм включает в себя вычисление меры подобия (или расстояния), между сигналом, полученным в момент времени t_i, и всеми путями решетки, входящими в каждое состояние в момент времени t_i. В алгоритме Витерби не рассматриваются те пути решетки, которые, согласно принципу максимального правдоподобия, заведомо не могут быть оптимальными. Если в одно и то же состояние входят два пути, выбирается тот, который имеет лучшую метрику; такой путь называется выживающим. Отбор выживающих путей выполняется для каждого состояния. Таким образом, декодер углубляется в решетку, принимая решения путем исключения менее вероятных путей. Предварительный отказ от маловероятных путей упрощает процесс декодирования. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия. Следует отметить, что задачу отбора оптимальных путей можно выразить как выбор кодового слова с максимальной метрикой правдоподобия или минимальной метрикой расстояния.