Кодек каскадного кода Хэмминга

Размещено на http://www.allbest.ru/

Министерство образования Республики Беларусь

Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники»

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

Кафедра сетей и устройств телекоммуникаций

Дисциплина Теория кодирования

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

на тему

КОДЕК КАСКАДНОГО КОДА

Студент: гр. 363101

Басык В. А.

Руководитель: доцент

Саломатин С.Б.

Минск 2016



Содержание

Введение

1. Область применения системы и описание процесса кодирования

1.1 Каскадные коды

1.2 Принцип построения помехоустойчивых кодов

1.3 Линейные блоковые коды

2. Расчет параметров кода

3. Разработка и обоснование структурной электрической схемы кодера и декодера

3.1 Разработка кодера Хэмминга

3.2 Разработка и обоснование структурной электрической схемы декодера

4. Разработка и обоснование функциональной электрической схемы кодера и декодера

4.1 Разработка и обоснование функциональной электрической схемы кодера

4.2 Разработка и обоснование функциональной электрической схемы декодера

5. Моделирование общего кодека

Заключение

Список источников литературы

декодер кодек помехоустойчивый электрический



Введение

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

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

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



1. Область применения системы и описание процесса кодирования

1.1 Каскадные коды

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

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

Код первой ступени называют также внутренним кодом. Процедура каскадного кодирования поясняется рис. 2.3.1. В результате кодирования получается двоичный блок длиной N · n, являющийся кодовой комбинацией каскадного кода [1].

В теории кодирования доказано, что построенный указанным способом каскадный код является линейным и его кодовое расстояние Dk не меньше, чем произведение кодовых расстояний внешнего (D) и внутреннего (d) кодов:



Dk > D · d.

Двоичная информационная последовательность, подлежащая кодированию каскадным кодом, поступает во внешний кодер, где разбивается на k-элементные блоки, каждый из которых рассматривается внешним кодером как q-ичный символ в двоичном представлении. Для каждых K таких q-ичных символов внешний кодер формирует N - K избыточных q-ичных символов, т. е. k-элементных блоков. Информационные и избыточные k-элементные блоки затем поступают во внутренний кодер, где преобразуются в кодовые комбинации двоичного (n, k)-кода [2].

1.2 Принцип построения помехоустойчивых кодов

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

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

Применение помехоустойчивых кодов для повышения верности передачи данных связанно с решением задач кодирования и декодирования. Задача кодирования заключается в получении при передаче для каждой k- элементной комбинации из множества qk соответствующего ей кодового слова длиною n из множества qn, т. Е. коды с исправляющей способностью (корректирующие) строятся так, что для передачи сообщения используются не все кодовые комбинации, а лишь некоторая их часть (так называемые разрешенные кодовые комбинации). Тем самым создается возможность обнаружения и исправления ошибки при неправильном воспроизведении некоторого числа символов. Корректирующие свойства кодов достигаются введением в кодовые комбинации дополнительных (избыточных) символов. Задача декодирования состоит в получении k-элементной комбинации из принятого n-разрядного кодового слова при одновременном обнаружении или исправлении ошибок.

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

При построении корректирующих кодов используют следующие основные параметры:

? основание кода (q) - число элементарных символов, выбранных для передачи сообщений. Если q=2, т.е. используются двоичные символы «1» и «0», то такие коды называются двоичными и кодирование производится в двоичном поле Галуа, т.е. GF(q)=GF(2). Если q>2, например, q=2m, m2, то такие помехоустойчивые коды называются недвоичными и кодирование информации производится в недвоичном поле Галуа, т.е. GF(qm)=GF(2m).

? длина кода (n) - число символов, выбранных для передачи сообщений, равняющееся количеству двоичных символов (бит) в данной кодовой последовательности;

? количество информационных символов (k) - количество двоичных символов, несущих полезную информацию;

? кодовое расстояние (d) - соответствует количеству позиций, которыми отличаются две сравниваемые кодовые последовательности; сравнивание кодовых последовательностей производится посимвольно (побитно) путём суммирования по модулю два;

? кратность (количество) исправляемых (tисп) и обнаруживаемых (tоб) ошибок;

? вероятность ошибочного декодирования (Pош) - вероятность появления неправильного кодового слова на выходе декодера;

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

? число проверочных позиций в коде r (r = n - k).

Основные зависимости между кратностью обнаруживаемых ошибок t0, исправляемых ошибок tu, исправлением стираний tc и кодовым расстоянием d0 кода:

Стиранием называется «потеря» значения передаваемого символа в некоторой позиции кодового слова, которая известна. Код, в котором каждое кодовое слово начинается с информационных символов и заканчивается проверочными символами, называется систематическим.

1.3 Линейные блоковые коды

Код называется групповым, если кодовые комбинации образуют некоторую подгруппу группы всех последовательностей длиной n

Линейные коды задаются с помощью порождающей матрицы G размерностью k*n и проверочной матрицы H размерностью r*n.

Матрицы между собой связаны уравнением:G*HT=0.

В качестве строк матрицы G выбираются линейно-независимые слова длиной n, отстоящие друг от друга на заданное кодовое расстояние d.

Так как линейно независимые векторы могут быть выбраны произвольным образом, то можно построить множество матриц G с одним и тем же кодовым расстоянием d.

Линейно независимые векторы инвариантны относительно двух операций, при выполнении которых минимальное расстояние кода не изменяется.

Так как линейно независимые векторы можно выбрать произвольно, то можно построить множество различных матриц G с одним и тем же кодовым расстоянием. Такие матрицы называются эквивалентными. Такие коды различаются различными проверочными символами при одинаковых информационных. С точки зрения алгебры, в проверочной матрице можно переставлять местами строки и столбцы и заменять i-ю строку на сумму i-й и j-й. Применяя эти операции можно привести матрицу G к приведено-ступенчатому виду:

где Ik - единичная матрица размерности k.

Таким образом, проверочная матрица будет иметь вид

Имея порождающую матрицу такого вида, для кодирования информационного слова А размерности k необходимо умножить вектор-строку А на порождающую матрицу G:

Проверочную матрицу Н возможно задать несколькими способами. Она должна содержать все ненулевые двоичные числа длины r. Наиболее часто используется метод с использованием элементов поля Галуа. Для формирования поля выбирается минимальный полином необходимой степени. На основе выбранного полинома записываются все элементы поля Галуа. Затем, записав коэффициенты степеней в таблицу, получим матрицу, которую затем, используя разрешенные алгебраические преобразования, доведем до приведено-ступенчатому вида [3].



2. Расчет параметров кода

В данном курсовом проекте используется код Хэмминга в качестве внешнего и внутреннего.

Код Хэмминга имеет параметры (n,k)=(2m-1;2m-1-m) и обычно задается проверочной матрицей. Кодовое расстояние dmin=3, т.е. коды Хэмминга исправляют любую одиночную и обнаруживают любую двойную ошибки. Если столбцы проверочной матрицы представляют упорядоченную запись десятичных чисел, т.е. 1,2,3... в двоичной форме, то вычисленный синдром однозначно указывает на номер позиции искаженного символа.

Заданные параметры кода Хэмминга:

? число идентифицируемых ошибок tоб=1;

? число исправляемых ошибок tис=1;

? число информационных позиций k=4;

? длина кода n=7.

Используя эти параметры рассчитаем параметры кода:

? кодовое расстояние d=2*tис+1=3;

? количество проверочных разрядов r= n-k=3.

Закодируем последовательность символов 1010 с помощью кода Хемминга. Для этого нужно умножить последовательность символов на порождающую матрицу G, которая выглядит следующим образом: А = [1010] * = 1010011.

Главной функцией кодера является формирование проверочных уравнений, правило формирования которых определено проверочной матрицей H. Чтобы получить проверочную матрицу, необходимо транспонировать информационные символы из матрицы G и добавить проверочные. Для (7,4)-кода Хэмминга проверочная матрица в упорядоченном виде имеет вид:

В матрице H(7, 4) символы a1, a2, a3, а4 - информационные, а a5, a6, a7 - проверочные, которые могут быть получены путем суммирования по модулю два определенных информационных символов.

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

а5= a1+ a2+ a3,

a6= a2+ a3+ a4,

a7= a1+ a2+ a4.

Устройство декодирования (декодер) вычисляет синдром, который реализуется блоком вычисления синдрома (БВС).

A*?HT = S=(S1, S2, S3)

C1C2C3C4C5C6C7

S11110100

S20111010

S31101001

S1 = c1+c2+c3+c5,

S2= c2+c3+c4+c6,

S3= c1+c2+c4+c7.

Вычисленный синдром поступает на селектор (дешифратор) синдрома, который по виду синдрома находит вектор ошибок E.

Если значение синдрома совпадает со значением i-го столбца матрицы H, то это значит, что ошибка произошла в i-м разряде. Если произошло две ошибки в i-м и j-м разрядах, то синдром S равен сумме i-го и j-го столбцов матрицы H. Поскольку это различные двоичные числа, то результат всегда не равен нулю и, следовательно, любая двойная ошибка будет обнаружена кодом Хэмминга.

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

Коррекция ошибок в принятом сообщении A* по вектору ошибок осуществляется в корректоре на сумматорах по модулю два.

Аналогичным образом проведем расчеты для кода Хемминга с параметрами (11, 7). Чтобы получить такие параметры, следует укоротить код с параметрами (15, 11).

Укороченные коды Хэмминга могут обеспечить:

1) упрощение кодирующих и декодирующих схем;

2) регулярность и однородность схем коррекции;

3) уменьшение вероятности неправильного (ложного) декодирования;

4) уменьшение вероятности неправильного (ложного) декодирования;

5) коррекцию двойных ошибок из-за отказов элементов и другие свойства.

Зададим проверочную матрицу для кода (15, 11):

Необходимо в проверочной матрице полного кода исключить любые 4 столбца, относящиеся к информационным разрядам, т.е. исключить нужное число столбцов весом w?2. Чем больше логических единиц в приписываемых строках проверочной матрицы, тем большей корректирующей способностью обладает разрабатываемый код, но тем больше будет иметь кодек сумматоров по модулю два и тем больше сложность его реализации. Следовательно, вычеркивание столбцов с максимальным весом приводит к уменьшению сложности вышеуказанных блоков. Проверочная матрица H укороченного кода (11, 7) имеет вид:

Матрица G выглядит следующим образом:

Закодируем последовательность, полученную на выходе предыдущего кода 1010011.

А= [1010011]* = 10100110100

Устройство кодирования реализует такие уравнения:

а8= а4+ а5+а6+а7,

а9= а2+а3+а6+а7,

а10=а1+а3+а5,

а11=а1+а2+а4+а7.

Вычисление синдрома:

c1c2c3c4c5c6c7c8c9c10c11

S100011111000

S201100100100

S310101000010

S411010010001

S1= c4+c5+c6+c7+c8,

S2= c2+c3+c6+c7+c9,

S3= c1+c3+c5+c10,

S4= c1+c2+c4+c7+c11.



3. Разработка и обоснование структурной электрической схемы кодера и декодера

3.1 Разработка кодера Хемминга

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

Информация поступает на вход схемы кодирования в параллельном виде. При помощи формирователя проверочных символов кодера (ФПСК) из информационных бит формируются проверочные разряды.

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

Для кода Хемминга с параметрами (11,7) структурная схема будет выглядеть, как показано на рисунке 4. Из 7 информационных бит будет сформировано 4 проверочных разряда.

3.2 Разработка и обоснование структурной электрической схемы декодера

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

Структурные электрические схемы кодеров Хемминга (7,4) и (11,7) представлены на рисунках 6 и 7 соответственно.



4. Разработка и обоснование функциональной электрической схемы кодера и декодера

4.1 Разработка и обоснование функциональной электрической схемы кодера

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

4.2 Разработка и обоснование функциональной электрической схемы декодера

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



5. Моделирование общего кодека

Наша модель будет состоять из 2 кодеков Хэмминга. Структурная схема включает в себя следующие блоки:

? кодер Хэмминга (7, 4);

? кодер Хэмминга (11, 7);

? бинарный симметричный канал;

? декодер Хэмминга (11, 7);

? декодер Хэмминга (7, 4).

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

Смоделированная в Matlab (2014) Simulink схема включает в себя следующее:

1) Бинарный генератор - устройство, которое случайным образом задает бинарную информационную последовательность.

2) 2 демультиплексора - извлекают компоненты входного сигнала и выводит компоненты в виде отдельных сигналов. Выходные сигналы упорядочены сверху порта.

3) 2 мультиплексора - объединяет свои входы в один выходной вектор. Элементы вектора выходного сигнала принять их порядок сверху вниз.

4) 2 кодера и 2 декодера Хэмминга, разработку которых мы провели в предыдущих разделах.

5) Unbuffer - преобразует параллельный код в последовательный.

6) Бинарный симметричный канал - передает наш код с кодера на декодер и формирует вектор ошибки.

Пример работы нашего кодека показан на рисунке.



Заключение

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

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

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



Список использованных источников

[1] Методы повышения энергетической и спектральной эффективности цифровой радиосвязи: учеб. пособие / В. А. Варгаузин, И. А. Цикин. ?СПб., 2013.

[2] Конопелько В.К., Липницкий В.А., Дворников В.Д. и др. Теория прикладного кодирования. Том 1, 2. - М.: БГУИР, 2004.

[3] Королев А.И. Коды и устройства помехоустойчивого кодирования информации. - М.: БГУИР, 2002.

Размещено на Allbest.ru