WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |
Г. И. Никитин СВЕРТОЧНЫЕ КОДЫ Учебное пособие 2001 УДК 621.391.254.019.4 (075) ББК 32.811.4 Н62 Никитин Г. И.

Н62 Сверточные коды: Учеб. пособие/ СПбГУАП. СПб., 2001. 80 с.: ил.

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

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

Рассмотрен порядок выполнения лабораторной работы "Сверточные коды".

Предназначено для радиотехнических специальностей всех форм обучения.

Рецензенты:

кафедра электронные вычислительные машины Санкт-Петербургского государственного университета путей сообщения;

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

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

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

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

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

Процессы кодирования и декодирования также осуществляются в непрерывном режиме.

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

Настоящее учебное пособие является дополнением лекционного курса “Радиотехнические системы передачи информации” [1]. В процессе изучения курса РТС ПИ студенты выполняют 4 лабораторных работы, связанные с теорией и практикой кодирования: “Первичные коды” [2], “Эффективные коды” [3], “Корректирующие коды” [4] и “Циклические коды” [5]. Изучив материалы данного учебного пособия, студенты должны выполнить 5-ю лабораторную работу “Сверточные коды”.

Материал пособия написан в соответствии с образовательным стандартом для инженеров: направление 654200 – “Радиотехника”, специализация 200700 – радиотехника; для магистров: направление 552500 – “Радиотехника”; для всех форм обучения: направление 654100 – “Электроника и микроэлектроника”, специализация 200400 – промышленная электроника.

Автор выражает признательность и благодарность студенту группы 2502 К. Б. Тисленко за помощь при подготовке материалов пособия, за написание раздела “Порядок выполнения лабораторной работы”, за подготовку программы выполнения работы на компьютерах.

1. ПЕРВЫЙ РЕКУРРЕНТНЫЙ КОД ФИНКА Первый непрерывный рекуррентный код был предложен в 1955 г. нашим соотечественником Л. М. Финком [6], который долгие годы заведовал кафедрой в Ленинградской военной академии связи, а затем работал в электротехническом институте связи им. М. А. Бонч-Бруевича.

Однако западные специалисты имели слабое представление о работах наших отечественных ученых в области кодирования и поэтому лишь спустя 4 года (в 1959 г.) “вновь открытый” рекуррентный код был назван по имени его западного автора – кодом Хегельбергера [7].

В этой связи целесообразно упомянуть самокритичное высказывание в предисловии к русскому изданию капитальной монографии У. Питерсона и Э. Уэлдона “Коды, исправляющие ошибки” [8]. Авторы по существу извиняются за недостаточное внимание к публикациям наших отечественных ученых в области теории и практики кодирования и отмечают следующее: “Без сомнения, наиболее серьезным пробелом данной монографии является отсутствия обзора последних работ, выполненных в Советском Союзе. Основные из этих работ включены в книгу В. Д. Колесника и E. Т. Мирончикова “Декодирование циклических кодов” (1968), заслуживающую самой высокой оценки [9]… В связи с этим, может быть, самым подходящим для данной книги явилось бы название “Коды, исправляющие ошибки, в Западном мире.” Отметим, что В. Д. Колесник и E. Т. Мирончиков в свое время закончили ЛИАП и в настоящее время (оба доктора технических наук и профессора) работают в ГУАП.



Итак, рассмотрим идею построения рекуррентного кода Финка в изложении самого Л. М. Финка, скромно умолчавшего в монографии “Теория передачи дискретных сообщений” [10] о своем авторстве.

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

a1b1 a2b2 a3b3 …….a kb k a k+1b ….

k+Информационные символы определяются передаваемым сообщением, а корректирующие формируются по следующему правилу:

bi = ak–S + ak+S+1 (mod2), (1.1) где s – произвольное целое число, называемое шагом кода (s = 0,1,2…).

Очевидно, что при ошибочном приеме некоторого корректирующего символа bi соотношение (1.1) в принятой последовательности не будет выполнено для i = k. В случае же ошибочного приема информационного символа a соотношение (1.1) не будет выполняться при двух i значениях k, а именно при k1 = i – s –1 и при k2 = i + s. Отсюда легко вывести правило исправления ошибок при декодировании. В принятой кодовой последовательности для каждого bk проверяется соотношение (1.1). Если оно оказалось не выполненным при двух значениях k (k = kи k = k2) и при этом k2 – k1 = 2s+1, (1.2) то информативный элемент ak1+S+1 должен быть заменен на противоположный.

Очевидно, что избыточность такого кода равна 1/2. Он позволяет исправлять все ошибочно принятые символы, кроме некоторых неудачных сочетаний. Так, если s = 0, он обеспечивает правильное декодирование, когда между двумя ошибочно принятыми символами имеется не менее трех (а в некоторых случаях двух) правильно принятых символов ( при этом учитываются как информационные, так и корректирующие символы).” Для наглядности в табл. 1.1, 1.2 и 1.3 графически показаны процессы форматирования (кодирования) кодов Финка при шагах s = 0,1 и соответственно. Там же представлены варианты декодирования принятых последовательностей с искаженными за счет помех различными символами. Искаженные символы и результаты их декодирования отображены в таблицах жирным шрифтом. Для всех рассматриваемых значений s = 0,1 и 2 принята исходная информативная последовательность из 10 символов 0001101011 (для s = 2 – с добавлением до 14).

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

Таблица. 1.S = Маркировка символов, a b a b a b a b a b a b a b a b a b a b 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 текущее значение i 1 2 3 4 5 6 7 8 9 Информационные символы, 0 0 0 1 1 0 1 0 1 суммирование по mod2, проверочные символы 0 0 1 0 1 1 1 1 Выходная последовательность 0 0 0 0 0 1 1 0 1 1 0 1 1 1 0 1 1 Декодирование при ошибке в одном информационном символе 0 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 1 0 Принятая последовательность, суммирование по mod 2, результат суммирования 0 0 1 1 0 1 1 1 Декодированная последовательность 0 0 0 1 1 0 1 0 Декодирование при ошибке в одном проверочном символе 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 Принятая последовательность, суммирование по mod 2, результат суммирования 0 0 1 0 1 1 1 1 0 0 0 1 1 0 1 0 Декодированная последовательность Декодирование при ошибке в двух проверочных символах Принятая последовательность, 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 1 1 0 суммирование по mod 2, результат суммирования 0 0 0 1 0 0 1 1 Декодированная последовательность 0 0 0 1 1 0 1 0 lc = Таблица. 1.S = Текущее значение i 1 2 3 4 5 6 7 8 9 Информационные символы, 0 0 0 1 1 0 1 0 1 суммирование по mod2, проверочные символы 1 1 0 0 1 1 Выходная последовательность 0 1 0 1 1 0 1 0 0 1 1 1 0 Декодирование при ошибке в одном информационном символе Принятая последовательность, 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 суммирование по mod 2, результат суммирования 0 1 0 1 1 1 Декодированная последовательность 0 0 1 1 0 1 Декодирование при пачке ошибок 3 символов 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 Принятая последовательность, суммирование по mod 2, результат суммирования 0 0 0 1 0 1 Декодированная последовательность 0 0 1 1 0 1 l = c Таблица. 1.S = i 1 2 3 4 5 6 7 8 9 10 11 12 13 0 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 Декодирование при пачке ошибок 5 символов 0 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1 0 1 1 lc = Полученные проверочные контрольные символы встраиваются между соседними информативными, образуя соответствующую входную последовательность, подлежащую передаче по каналу связи.

На стороне приема осуществляется та же самая процедура получения проверочных символов, что и на стороне передачи (1.1), и производится сравнение их с принятыми проверочными символами. Если при приеме ошибок нет, то результат суммирования по модулю 2 (сравнение) будет состоять из последовательности, содержащей одни нули. Эта последовательность, так же как в блочных циклических кодах, называется синдромом. Напомним [5], что термин “синдром” заимствован из медицинской практики (с греческого – вместе бегущий) и означает сочетание симптомов болезни, характерное для данного заболевания.





В теории кодирования синдром, который также называют опознавателем ошибок, означает совокупность признаков, характерных для определенных ошибок. Синдром полностью определяется комбинацией ошибок, которые приводят к появлению в синдромной последовательности 1 на соответствующих позициях. В табл.1.1–1.3 непосредственно синдромы только с 1 на позициях, определяющих конфигурацию ошибок, не указаны. Их заменяют результаты суммирования по модулю 2 по алгоритму (1.1) информационных символов ai, принимаемых с ошибками, причем символы, определяющие конфигурацию ошибок, выделены в таблицах жирным шрифтом.

Как видно из табл. 1.1, при s = 0 ошибка при приеме одного 5-го информационного символа приводит при декодировании к ошибке двух проверочных символов 4-го и 5-го, что позволяет исправить находящийся между ними 5-й информационный символ, в соответствии с выражениями (1.1) и (1.2).

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

Декодирование при ошибке в двух информационных символах (табл. 1.1, s = 0) показывает, что для верного декодирования ошибочные символы (4-й и 6-й) должны быть разнесены, чтобы не участвовать в формировании одинаковых проверочных символов. Для этого номера набора искаженных проверочных символов в результате суммирования должны стыковаться без перекрытия и, по крайней мере, без пропуска.

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

Это условие “стыковки” требует наличия трех (l = 3) верно приниc маемых символов между двумя искаженными информационными символами. Назовем этот интервал l – расстоянием стыковки.

c В этом случае, когда соотношение (1.1) оказывается не выполненным для группы проверочных символов с 3-го по 6-й, в соответствии с выражением (1.2) 4-й и 6-й информационные элементы заменяются на противоположные, т. е. происходит верное исправление ошибочно принятых информационных символов с номерами i = 4 и i = 6. Однако в интервал стыковки l = 3 попадает верно принимаемый 5-й информационный символ, для c которого из-за ошибочно принятых соседних (левого 4-го и правого 6-го) информационных символов также будет выполняться условие (1.2) и он, верно принятый, будет в декодере заменен на противоположный.

Для того чтобы этого не произошло необходимо увеличить число верно принимаемых символов между ошибочными информационными по крайней мере на два, чтобы пары неверно декодируемых проверочных символов не стыковались. Это приводит к тому, что стыковочное расстояние l = 3 требуется увеличить по крайней мере (для s = 0) на lД = c (два дополнительных символа). Таким образом, для однозначного декодирования информационных символов требуется между двумя ошибочно принимаемыми символами иметь защитный интервал l0 = l + lД из c верно принимаемых символов с учетом проверочных. Для кода Финка с шагом s = 0 значение l0 = 5. Увеличение шага (s>0) способствует возможности исправления не только ошибочных символов в принимаемой последовательности, но и групп подряд следующих символов. При s = код Финка не способен исправлять даже два подряд следующих ошибочных символа, а при шаге s = 1 появляется возможность исправления групп из трех соседних символов.

Подобные “серийные” ошибки возникают в результате воздействия в каналах передачи помех импульсного характера, длительность которых больше длительности одного символа. Аналогичная ситуация возникает и в каналах с кратковременными замираниями сигнала (мультипликативная помеха), в частности, в системах подвижной связи [11].

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

В этой связи интересно привести высказывание редактора перевода монографии [7] Добрушина Р.А.: “При переводе книги возникли серьезные терминологические трудности, связанные с отсутствием или неоднозначностью русской терминологии. Так, после долгих размышлений в качестве перевода английского термина burst of error был выбран термин “пачка ошибок”, хотя в русской литературе встречаются и другие варианты (“пакет ошибок”, ”вспышка ошибок” и т. п.)”. В дальнейшем, присоединяясь к мнению Добрушина Р. Л., будем пользоваться термином пачка (пакет) ошибок.

Пачка ошибок длиной b определяется вектором ошибки, в котором все единицы заключены в последовательности b символов при условии, что крайние символы этой последовательности – единицы. Так, векторы ошибок при пачке ошибок длиной b = 4 могут выглядеть следующим образом (для последовательности длиной n = 10): 0001101000, 0100100000, 0000011110 и т. п.

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

Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.