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

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

 

ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

 

Факультет прикладной математики и телекоммуникаций

 

Кафедра радиоэлектронных средств

 

 

Е. В. МЕДВЕДЕВА

А. В. ЧАСТИКОВ

В. Н. ШАКИН

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

В РАДИОТЕХНИКЕ И СВЯЗИ

 

Утверждено пленумом Совета УМО

по образованию в области телекоммуникации

в качестве учебного пособия

 

Киров 2004

Печатается по решению редакционно-издательского совета

Вятского государственного университета

 

УДК 621.391

 

М 42

 

Рецензенты: заместитель технического директора

ОАО “Волга Телеком” А. Б. Герасимчук;

заведующий кафедрой «Радиоэлектронные средства»

доктор технических наук, профессор Е. П. Петров

 

Медведева Е. В. Помехоустойчивые коды в радиотехнике и связи: Учебное пособие / Е. В. Медведева, А. В. Частиков, В.Н. Шакин. - Киров: Изд-во ВятГУ, 2004. - 68с.

 

 

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

Приводятся описания визуальной инструментальной системы «Ecclabs» для построения помехоустойчивых кодов, проведения кодирования и декодирования и визуальной инструментальной системы «Code» для построения частотно-компактных кодов и расчета их характеристик.

Пособие содержит примеры построения кодов, контрольные вопросы и методические задания к лабораторным работам по дисциплинам «Теория информации и кодирования» и может быть полезно для студентов специальностей: 201800 «Защищенные системы связи», 200900 «Сети связи и системы коммутации», 201500 «Бытовая радиоэлектронная аппаратура».

 

 

Редактор Е. Г. Козвонина

 

Подписано в печать Бумага офсетная Зак.№ 394

Печать копир Aficio 1022 Усл.печ.л. 4,25 Тир. 52 Бесплатно

 

Текст напечатан с оригинала-макета, предоставленного авторами

610000, г. Киров, ул. Московская, 36.

Оформление обложки, изготовление – ПРИП ВятГУ.

ã Е. В. Медведева, 2004

ã А. В. Частиков, 2004

ã В. Н. Шакин, 2004

ã Вятский государственный университет, 2004

 

ОГЛАВЛЕНИЕ

 

Введение.......................... Глава 1. Помехоустойчивые коды................ 1.1. Основные характеристики помехоустойчивых кодов...... 1.2. Коды, обнаруживающие ошибки............... 1.2.1. Двоичный безызбыточный код............... 1.2.2. Код с защитой по паритету (четности, нечетности)...... 1.2.3. Код с простым повторением................ 1.2.4. Код с повторением и инверсией.............. 1.2.5. Код на одно сочетание.................. 1.3. Коды, исправляющие ошибки................ 1.3.1. Общие правила построения блочных кодов.......... 1.3.2. Правила построения кода Хэмминга............. 1.3.3. Правила построения кода Рида-Маллера........... 1.3.4. Основные понятия о свойствах многочленов и полях Галуа... 1.3.5. Правила построения примитивных кодов БЧХ........ 1.3.6. Правила построения кода Голея............... 1.3.7. Правила построения кода Рида-Соломона.......... 1.3.8. Правила построения кода Вайнера-Эша........... 1.3.9. Правила построения кода Ивадаре............. 1.4. Кодирование и декодирование кодов............ 1.4.1. Схемы кодирования и декодирования циклических кодов.... 1.4.2. Схемы кодирования и декодирования линейных кодов..... 1.4.3. Схемы кодирования и декодирования свёрточных кодов.... 1.5. Описание инструментальной системы для построения помехоустойчивых кодов.................... 1.5.1. Установка инструментальной среды на ПЭВМ........ 1.5.2. Интерфейс инструментальной среды............. 1.6. Методика построения кодов в инструментальной среде "Помехоустойчивые коды"................... 1.6.1. Код Хэмминга...................... 1.6.2. Код Рида-Маллера.................... 1.6.3. Код БЧХ........................ 1.6.4. Код Голея........................ 1.6.5. Код Рида-Соломона................... 1.6.6. Код Вайнера-Эша.................... 1.6.7. Код Ивадаре....................... 1.7. Вычисление характеристик кодов.............. 1.7.1. Вычисление энергетической эффективности кода....... 1.7.2. Вычисление корреляционных функций кода......... 1.8. Построение кодирующих и декодирующих схем.......... 1.9. Задание к лабораторной работе «Построение и расчет параметров помехоустойчивых кодов»............... 1.10. Контрольные вопросы к главе 1.............. Глава 2. Коды для линий связи................. 2.1. Особенности линейных кодов................ 2.2. Параметры и характеристики линейных кодов......... 2.3. Правила построения линейных неалфавитных кодов...... 2.3.1. Код без возвращения к нулю (NRZ, БВН).......... 2.3.2. Код с возвращением к нулю (RZ).............. 2.3.3. Код с чередованием полярности импульсов (AMI)....... 2.3.4. Код с высокой плотностью единиц (HDB-3, КВП-3)...... 2.3.5. Биполярный код с замещением трех нулей (В3ZS)....... 2.3.6. Парноизбирательный троичный код (ПИТ, PST)....... 2.3.7. Код с инверсией токовых посылок (CMI).......... 2.3.8. Код с поразрядно чередующейся инверсией (ADI)....... 2.3.9. Абсолютный биимпульсный код (АБС)........... 2.3.10. Относительный биимпульсный код (ОБС).......... 2.3.11. Код Миллера...................... 2.3.12. Код DMI........................ 2.3.13. Код H......................... 2.3.14. Код ISDN....................... 2.3.15. Квазитроичный разностный код (PRKK).......... 2.4.Правила построения линейных алфавитных кодов........ 2.4.1. Код 4B3T........................ 2.4.2. Код FOMOT....................... 2.4.3. Код MS43........................ 2.5. Правила построения многоуровневых кодов (МУР)....... 2.6. Описание программы Code................. 2.7. Задание к лабораторной работе «Построение и расчет параметров кодов для линий связи»............... 2.8. Контрольные вопросы к главе 2............... Глава 3. Псевдослучайные последовательности.......... 3.1. М-последовательности.................... 3.2. Задание к лабораторной работе «Построение и расчет характеристик псевдослучайных сигналов»............ 3.3. Контрольные вопросы к главе 3............... Библиографический список...................

- - - - - - - -   -   - - - - - - -   - - - - - - - - - - - - - - -

 

 

ВВЕДЕНИЕ

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

Особый класс помехоустойчивых кодов образуют частотно-компактные коды или коды для линий связи [16-24]. Они предназначены для сосредоточения энергии сигнала в возможно более узкой полосе частот. Кроме того, линейный код должен осуществлять контроль ошибок на физическом уровне и не должен приводить к их размножению. Столь общая постановка задачи понимается в различных системах по-разному. В проводных линиях связи и линейных трактах, содержащих полосно-ограничивающие фильтры с крутыми фронтами, необходимо основную энергию сигнала «отодвинуть» от крайних частот к центру полосы пропускания с целью уменьшения межсимвольных искажений. В сетях радиосвязи с жесткими ограничениями по электромагнитной совместимости радиосредств кодирование должно обеспечить значительное (десятки децибел) уменьшение уровня внеполосных излучений.

В настоящее время большую часть цифровых СПИ составляют широкополосные системы. Они применяются практически во всех областях – от персональных систем связи до беспроводных локальных компьютерных сетей – и постепенно вытесняют традиционные средства передачи информации. Основными преимуществами широкополосных СПИ являются [25-32]:

· высокая помехозащищенность;

· электромагнитная совместимость с другими радиоэлектронными средствами;

· сложность перехвата сообщений;

· обеспечение кодовой синхронизации большого числа абонентов при работе в общей полосе частот;

· возможность совмещения приема информации и измерения параметров движения объекта.

Указанные преимущества еще более подчеркиваются и становятся очевидными при использовании шумоподобных сигналов (ШПС) с большими базами.

Основой для формирования ШПС служат псевдослучайные кодовые последовательности (ПСП), используемые для модуляции сигнала несущей частоты.

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

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

Во второй части изложены правила построения и расчет параметров кодов для линий связи. Рассмотрены особенности работы в инструментальной системе Code, предназначенной для построения и исследования частотно-компактных кодов.

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

Каждая часть пособия завершается заданиями по исследованию кодов для лабораторных работ.

Пособие предназначено для студентов специальностей 200900 «Сети связи и системы коммутации», 201800 «Защищенные системы связи» 201500 «Бытовая радиоэлектронная аппаратура» по дисциплинам “Системы документальной электросвязи” и “Теория информации и кодирования”.

 

ГЛАВА 1. ПОМЕХОУСТОЙЧИВЫЕ КОДЫ

 

Пример

- 1-я кодовая комбинация     - 2-я кодовая комбинация - сумма по модулю 2.

Число единиц в сумме (вес суммы) равно кодовому расстоянию .

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

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

Таблица 1.1

На основании табл.1.2 получим распределение рабочих кодовых комбинаций по кодовым расстояниям (табл.1.1).

Таблица1.2

Из анализа табл.1.2 ясно, что, например, кодовый вектор отстоит от одного из векторов на величину и от двух других - на , а вектор отстоит от двух векторов на и от одного на . Введем обозначение - число рабочих кодовых векторов, отстоящих от данного вектора на . Коды, для которых число различно для разных кодовых векторов, называются несимметричными. Если число для всех рабочих кодовых векторов одинаково, то код называется симметричным.

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

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

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

,

(1.3)

где - общее число кодовых векторов, отстоящих от данного вектора на кодовое расстояние .

Для симметричных кодов число одинаково для всех рабочих кодовых векторов, и коэффициент определяется согласно (1.3). Для несимметричных кодов коэффициент ложных переходов при -кратной ошибке определяется как среднее значение этого коэффициента для всех рабочих кодовых векторов, т.е.

.

(1.4)

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

.

(1.5)

Для рассматриваемого примера найдем коэффициент ложных переходов

при ;

при ;

при .

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

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

Энергетическим выигрышем кода (ЭВК) называют величину

,

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

Быструю ориентировочную оценку энергетической эффективности для оперативного сравнения кодов осуществляют по величине .

Корреляционные свойства кодов оценивают апериодической функцией автокорреляции (АКФ) и несколькими видами функции взаимной корреляции (ВКФ): апериодической, периодической, смешанно-периодической.

Для кодового слова X, состоящего из символов , апериодическую АКФ определяют как .

ВКФ вычисляют для совокупности двух или трех кодовых слов (слова состоят из символов , ). Апериодическая ВКФ между словами X и

;

периодическая ВКФ между тремя словами и

;

смешанно-периодическая ВКФ между словами и

.

 

Коды, обнаруживающие ошибки

Двоичный безызбыточный код

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

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

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

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

 

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

 

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

Пример. Рабочие комбинации кода с простым повторением (табл.1.4).

Таблица 1.4

	Код с повторением
	000 000
	001 001
	010 010
	011 011
	100 100
	101 101
	110 110
	111 111

 

Код позволяет обнаружить все ошибки нечетной кратности и значительную часть ошибок четной кратности.

 

Код на одно сочетание

 

Числовой -разрядный двоичный код позволяет иметь различных кодовых комбинаций. Число может быть представлено как сумма сочетаний из по 0,1,2,…, ,…, , т.е.

.

Таким образом, двоичный безызбыточный код есть код на все сочетания, так как его мощность . Мощность кода на одно сочетание . Код образуется из двоичного безызбыточного кода путем отбора кодовых комбинаций, имеющих одинаковое число единиц. Так, для =3 из восьми возможных кодовых комбинаций код на одно сочетание составляет лишь три кодовых вектора: 011,101 и 110.

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

 

Коды, исправляющие ошибки

Основные понятия о свойствах многочленов и полях Галуа

 

Операции над коэффициентами полиномов циклических кодов производятся в алгебраической системе, которая носит название поля Галуа.

Полем Галуа называется конечное коммутативное поле. Конечное поле - это конечное множество из q элементов, в котором определены правила для выполнения арифметических операций. Поле Галуа из элементов обозначается .

Поля Галуа обладают следующими свойствами:

- в поле определены две операции: сложение и умножение;

- результатом сложения или умножения двух элементов поля является элемент этого же поля;

- поле всегда содержит мультипликативную единицу 1 и аддитивную единицу 0, т.е. и для любого элемента , принадлежащего полю;

- для любого элемента , не равного нулю, существует обратный элемент по сложению (минус ) и по умножению (), такой, что и (в случае обратный элемент совпадает с самим элементом);

- выполняются обычные правила ассоциативности , коммутативности и дистрибутивности .

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

Если - простое число, то элементами поля являются числа 0, 1,..., ( -1), а сложение и умножение являются обычными сложением и умножением по модулю .

Если является степенью простого числа, т.е. если , то элементами поля являются все многочлены степени или менее, коэффициенты которого лежат в простом поле .

Правила умножения и сложения таких многочленов получаются из обычного умножения и сложения многочленов и последующего приведения результата по модулю некоторого специального многочлена степени . Этот многочлен обладает тем свойством, что его нельзя разложить на множители, используя только многочлены с коэффициентами из поля . Такие многочлены называются неприводимыми, они аналогичны простым числам. Как и простые числа, они могут находиться методом перебора. Для двоичных кодов такие многочлены должны быть неприводимыми над полем . Наиболее подробная таблица неприводимых над полем многочленов представлена в [2,4,10].

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

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

Пусть неприводимый многочлен имеет вид

.

(1.19)

Пусть - примитивный элемент поля . Если неприводимый многочлен примитивный, то .

Запись поля Галуа осуществляется в виде набора из многочленов степени, не превышающей . Первый элемент записи всегда равен нулю (нулевой элемент поля) и обычно в записи не приводится. Остальные многочленов представляют собой степени от 0 до примитивного элемента поля. Здесь и далее принимается, что старшие степени многочленов записываются слева, младшие справа.

Построение поля проводится в следующем порядке:

- записываются степени примитивного элемента от 0 до (m -1); запись производится в виде

- записывается элемент , который определяется по правилу

;

- записываются многочлены, соответствующие остальным степеням , от до . Указанные степени определяются посредством: а) умножения предыдущего многочлена, т.е. многочлена, соответствующего , на ; б) замены на многочлен ; в) приведения подобных членов.

Таким образом, поле Галуа GF(2^m) запишется в виде

(1.20)

Умножение элементов поля Галуа сводится к сложению степеней умножаемых элементов и приведению результата в диапазон … . Операция сложения элементов поля Галуа выполняется над двоичными числами по модулю 2. Степень определяется по соответствию результата сложения в поле вида (1.20).

Пример. Многочлен является неприводимым примитивным многочленом третей степени. Следовательно, при помощи этого многочлена может быть построено поле . Согласно формулам (1.20), поле будет иметь вид

 

.

(1.21)

В соответствии с (1.21) выражение можно вычислить следующим образом: a² + a⁵ = a³ = (011); a³a = a⁴ = (110); 1 + a³ = a = (010); aa = a² = (100); a⁴ + a² = a = (010). Таким образом, искомое выражение будет равно ¦(a) = a = (010).

Также для построения поля Галуа важны следующие свойства:

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

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

- если - корень многочлена , то называется минимальной функцией , если - примитивный элемент, то ¦(x) называется примитивным многочленом;

- корни многочлена совпадают с ненулевыми элементами .

Пример. Многочлен неприводим над полем , но он может быть разложен на множители над полем . Если поле GF (2³) задано в соответствии с (1.21), то подстановкой можно найти, что a является корнем . Действительно, ¦(a) = a³ + a + 1 = (011) + (010) + (001) = (000) = 0. Также корнями являются a² и a⁴, что можно проверить подстановкой. У неприводимого многочлена над полем может быть не более m корней. Дальнейшее повышение степени a дает повторение тех же самых корней (, a² и a⁴), действительно, a⁸ = a, a¹⁶ = a² и т.д. Многочлен может быть также получен, если известно, что a, a² и a⁴ являются корнями одного и того же многочлена. Например, .

Элемент a является примитивным элементом поля GF (2³), поэтому является примитивным многочленом. Многочлен (x⁷-1) разлагается на множители следующим образом: (x⁷-1) = (x³+x²+1)(x³+x+1)(x+1). Корнем примитивного многочлена (x+1) является a⁰ = 1, корнями (x³+x+1) - a, a², a⁴; корнями (x³+x²+1) - a³, a⁶, a¹²=a⁵. Все эти семь корней являются ненулевыми элементами поля GF (2³), состоящего как раз из семи ненулевых элементов.

 

Способ 1

Кодовая комбинация циклического кода равна:

= = .

Другие кодовые комбинации циклического кода могут быть получены путем циклического сдвига данной кодовой комбинации.

Процесс умножения двух полиномов реализуется схемой, показанной на рис.1.6.

 

 

Рис.1.6

 

Для двоичных кодов существенны только те цепи умножения, в которых .

Способ 2

Кодовую комбинацию для получения разделимого кода получают по алгоритму: