Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

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

.pdf
Скачиваний:
19
Добавлен:
30.01.2019
Размер:
601.36 Кб
Скачать

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

УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«Санкт-Петербургский государственный университет телекоммуникаций им. Проф. М. А. Бонч-Бруевича»

Кафедра «Сетей связи и передачи данных (СС и ПД)»

Курсовой работа по дисциплине: «Математические модели процессов обработки данных»

ИССЛЕДОВАНИЕ ПРИНЦИПОВ КОДИРОВАНИЯ И ДЕКОДИРОВАЯ КОДОВ БЧХЭ

Выполнил: Вариант 21

Проверил: Охорзин В.М.

Санкт-Петербург

 

Оглавление

 

Цель работы..................................................................................................................................

3

Исходные данные.........................................................................................................................

3

1.

Код (15,6) БЧХЭ. Характеристический многочлен ........................................................

3

Ход работы....................................................................................................................................

5

1.

Кодирование ........................................................................................................................

5

2.

Декодирование с гарантийно исправляемой ошибки. .....................................................

6

3.

Декодирование с гарантийно неисправляемой ошибкой ..............................................

10

4.Декодирование с гарантийно неисправляемой ошибкой с предварительной

децимацией ...............................................................................................................................

12

Список литературы...................................................................................................................

14

2

Цель работы

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

Исходные данные

1. Код (15,6) БЧХЭ. Характеристический многочлен.

Двоичная рекуррентная последовательности длины n=15 порождается примитивным многочленом степени 4 с корнями и поля GF(24). Этот многочлен должен быть сомножителем 15 + 1. В табл. 1 приведены неприводимые сомножители 15 + 1, их корни в виде элементов поля GF(24), значения функций-след этих элементов и периоды рекуррентных последовательностей, порождаемых представленными многочленами.

Таблица 1. Неприводимые сомножители 15 + 1 и их характеристики.

 

 

 

 

 

 

 

 

Функция-

 

Период

Обозначение

Многочлен

 

 

 

Корни

 

 

последова-

п/п

 

 

 

 

след ( )

 

 

 

 

 

 

 

 

 

 

 

4

 

тельности

 

 

 

 

 

 

 

 

 

 

 

 

1

( )

4 + + 1

 

 

1, 2, 4, 8

 

0

 

 

 

15

 

1

 

 

 

 

 

 

 

 

 

 

 

 

2

( )

4 + 3 + 2 + + 1

 

3, 6, 9, 12

 

1

 

 

 

5

 

2

 

 

 

 

 

 

 

 

 

 

 

 

3

( )

2 + + 1

 

 

 

5, 10

 

0

 

 

 

3

 

3

 

 

 

 

 

 

 

 

 

 

 

 

4

( )

4 + 3 + 1

 

 

7, 11, 13, 14

 

1

 

 

 

15

 

4

 

 

 

 

 

 

 

 

 

 

 

 

5

( )

+ 1

 

 

15 = 0

 

0

 

 

 

1

 

5

 

 

 

 

 

 

 

 

 

 

 

 

 

Согласно заданию, выберем характеристический многочлен для кода (15,6) в виде:

P( ) = (4 + + 1)(2 + + 1) = 6

+ 5 + 4 + 3 + 2

+ +

= 6 +

 

 

0

1

 

2

3

4

5

6

 

6 + 5 + 4 + 3 + 1, из чего следует, что

=

=

=

= = 1 и

+ = 0.

 

 

 

0

1

2

3

6

4

5

 

 

Рекуррентное

выражение, которому

должны

соответствовать

связи

между

символами кодовой комбинации кода с данных характеристическим многочленом имеет вид: +6 = +5 + +4 + +3 + . Порождающий многочлен данного кода (15,6) имеет вид среди своих корней пять подряд идущих степеней примитивного элемента поля GF(24):11, 12, 13, 14, 15, т.е. минимальное кодовое расстояние данного кода (15,6) равно 6 и этот код способен гарантийно исправить все однократные и двухкратные ошибки.

3

2. Таблица исходных данных

 

 

Таблица 2. Исходные данные.

 

 

 

(C, D)

1( )

2( )

( 3, 2)

12 + 11

11 + 9 + 7

Значения C = и D = , являются элементами поля GF(22) и GF(24).

 

Таблица 3. Элементы полей GF(22) и GF(24).

 

Формы элементов

 

Целочисленная

Степенная

Векторная 0, 1, 2, 3

0

−∞

0000

1

0 = 1 = 15 = −15

1000

2

= −14

0100

3

2 = −13

0010

4

3 = −12

0001

5

4 = 1 + = −11

1100

6

5 = + 2 = −10

0110

7

6 = 2 + 3 = −9

0011

8

7 = 1 + + 3 = −8

1101

9

8 = 1 + 2 = −7

1010

10

9 = + 3 = −6

0101

11

10 = 1 + + 2 = −5

1110

12

11 = + 2 + 3 = −4

0111

13

12 = 1 + + 2 + 3 = −3

1111

14

13 = 1 + 2 + 3 = −2

1011

15

14 = 1 + 3 = −1

1001

 

 

 

 

Формы элементов

 

Целочисленная

Целочисленная

Целочисленная

0

−∞

00

1

0 = 1 = 3 = −3

10

2

1 = −2

01

3

2 = 1 + = −1

11

4

Ход работы

1. Кодирование

Схема кодирующего устройства рассматриваемого кода БЧХЭ (15,6), может быть реализована на регистрах сдвига с обратными связями как показано на рисунке 1.

Рисунок 1. Схема кодирующего устройства кода БЧХЭ (15,6).

Для кода БЧХЭ (15, 6) с заданными характеристическим многочленом

P( ) = ( 4 + + 1)( 2 + + 1) = 0 6 + 1 5 + 2 4 + 3 3 + 4 2 + 5 + 6 = 6 +6 + 5 + 4 + 3 + 1, построить схему кодера и с её помощью сформировать кодовую

комбинацию f(x) по заданной информацией последовательности (C, D), где С – последовательность из четырёх информационных символов, а D – из двух. Верхний регистр является генератором элементов поля GF(24), а нижний – генератор элементов поля GF(22). При поступлении в кодер кодируемой последовательности (C, D) элементов C параллельным кодом вводятся в ячейки верхнего регистра, а D – нижнего. После этого генераторы запускаются и подают на вход сумматор пятнадцатиэлементные последовательности {u} и {y} соответственно.

Последовательность {u} – это последовательность максимальной длины с характеристическим многочленом 4 + + 1, т.е. комбинация циклического кода (15,4). Последовательность {y} – это пятикратно повторенная последовательность максимальной длины с характеристическим многочленом 2 + + 1, т.е. комбинация циклического кода (3,2). Начальными фазами этих последовательностей максимальной длины являются информационные символы C = и D = , представленные элементами поля GF(24)( ) и GF(22)( ) соответственно. На выходе сумматора формируется результирующая последовательность {s} – комбинация неразделимого (несистематического) циклического кода БЧХЭ (15,6). Как исходные {u} и {y}, так и результирующая {s} последовательности могут быть представлены через совокупности функции-след:

{ } = {T ( +14) … T ( )}, { } = {T ( +2) … T ( )}, { } = {[T ( +14) + T ( +2)] … [T ( ) + T ( )]}.

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

5

Таблица 4. Результаты расчётного кодирования.

 

 

 

 

 

 

 

 

 

 

 

( ) + T ( )

 

 

 

 

 

 

 

 

T

тактов

 

 

 

 

 

= T ( )

 

 

 

= T ( )

 

 

4

2

 

0

1

 

2

3

4

0

 

1

2

 

 

0

0

0

 

0

 

1

1

 

 

1

 

-

1

1

1

 

0

 

0

1

 

 

0

 

0

2

0

1

 

1

 

0

0

 

 

1

 

0

3

0

0

 

1

 

1

1

 

 

1

 

1

4

1

1

 

0

 

1

1

 

 

0

 

0

5

1

0

 

1

 

0

0

 

 

1

 

1

6

0

1

 

0

 

1

1

 

 

1

 

1

7

1

1

 

1

 

0

1

 

 

0

 

0

8

0

1

 

1

 

1

0

 

 

1

 

0

9

1

1

 

1

 

1

1

 

 

1

 

0

10

1

0

 

1

 

1

1

 

 

0

 

0

11

1

0

 

0

 

1

0

 

 

1

 

1

12

1

0

 

0

 

0

1

 

 

1

 

0

13

0

1

 

0

 

0

1

 

 

0

 

1

14

0

0

 

1

 

0

0

 

 

1

 

0

15

0

0

 

0

 

1

1

 

 

1

 

1

Рисунок 2. Результат программной модели кодера.

Врезультате кодирования заданной информационной последовательности (C, D) сформировали следующую кодовую комбинацию f(x) = 101010000110100.

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

Поскольку GF(22) является подполем GF(24), то элементу из поля GF(22) соответствует элемент 5 из поля GF(24) и любой элемент последовательности {s} может быть представлен в виде = T4( ) + T4\2[( 5) ( 3)]. Нижний индекс функции-след

T4\2[( 5) ( 3)] указывает, что 5 – элемента поля GF(22), а функция-след T4\2[( 5) ( 3)] должна вычисляться для поля GF(24).

2. Декодирование с гарантийно исправляемой ошибки.

Декодирование кодов БЧХЭ представляет собой мажоритарное декодирование комбинаций кодов БЧХЭ по k – элементным участкам на основе двойственного базиса

GF(p ).

Поскольку комбинации кода БЧХЭ представляют собой линейные рекуррентные последовательности, декодировать БЧХЭ означает то же самое, что найти начальные m

элементов (обозначаемые C , где

C элементы поля GF(p )), которые формируют

 

i

 

6

переданную последовательность. Эти элементы и являются информационными в кодах БЧХЭ.

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

C = +−1 , (1)

=1

с помощью этой формулы по каждому из 2 − 1, m – элементных участков замкнутого в кольцо вектора принятой последовательности S рассчитываются совместные значения коэффициентов Ci для каждого неприводимого многочлена из разложения многочлена P(x).

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

Таким образом, для построения декодера необходимо предварительно рассчитать только коэффициенты Ci, которые однозначно определяются коэффициентами

проверочного многочлена P(x). Коэффициенты ,

определяются по формуле (2).

 

 

, =

=0

= =

 

(2)

( )

 

 

 

 

Рисунок 3. Схема декодирующего устройства кода БЧХЭ (15,6).

Схема декодирующего устройства кода БЧХЭ состоит из входного регистра, генераторов обратных элементов поля GF(22) и GF(24), шести умножителей обратных

7

элементов поля GF(22) на коэффициенты , шести умножителей обратных элементов поля GF(24) на коэффициенты , двенадцати ключевых схем – по одной на выходе каждого умножителя, схемы суммирования элементов поля GF(24) и схемы суммирования элементов поля GF(22), на выходах которых формируются предварительные значения фрагментов переданного сообщения C и D соответственно, а также мажоритарного элемента, выносящего решение о принятом сообщении (C, D) по большинству совпадений пар принятых от схем суммирования значений (C, D).

Генератор обратных элементов поля GF(2 ) представляет собой генератор элементов поля GF(2 ) с изменённым на противоположное направление перемещения информации по регистру.

Рисунок 4. Генераторы обратных элементов поля: а − (22) ,б − (24).

Для декодирования последовательности внесём соответствующие ошибки в последовательность, определённые вариантом задания. Многочлен 1( ) = 12 + 11 определяет ошибки в принятой комбинации.

Выполним декодирование последовательности 1( ) = ( ) + 1( ), где 1( )- гарантийно исправляемый кодом БЧХЭ (15,6) многочлен ошибок, f(x) – комбинация кода (15,6), с формированная в кодирующем устройстве. Операция внесения ошибки в исходную кодовую последовательность:

( ) = 1010100001101001( ) = 12 + 11

1( ) = 101010000111000

Процесс декодирования отображен в табл. 5.

Выводы по результатам декодирования последовательности 1( ) = ( ) + 1( ). Согласно процессу декодирования, отображенному в табл. 5 и принципу мажоритарного декодирования было выявлено 8 совпадений декодированных последовательностей (C, D) = (0001 11) = ( 3, 2), которые являются исходными информационными элементами. Так как минимальное кодовое расстояние данного кода (15,6) равно 6, то код способен гарантийно исправить все однократные и двухкратные ошибки, что было доказано при выполнении декодирования комбинации вида 1( ) = ( ) + 1( ), имеющий две не сгруппированные ошибки.

8

Таблица 5. Декодирование последовательности 1( ) с гарантийно исправляемой ошибкой.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Вычисление значения Сi

 

 

 

Вычисление значения Di

 

Результат декодирования

Такты

 

S

 

S

 

S

 

S

 

S

S

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

i

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Число

 

 

 

 

 

 

 

 

 

 

 

 

 

 

С

ε-i

 

ε5

ε9

1

ε2

ε3

ε4

ε-iΣ

D

ε-i

1

ε10

0

1

ε5

ε10

ε-iΣ

i, Di)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

совпадений

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

1

1

 

0

 

0

 

0

С0

1(

 

ε5

ε9

1

 

 

)=

ε13

D0

1(

1

ε10

0

 

 

)=

ε5 = µ

1011 01

1

1

0

1

1

 

1

 

0

 

0

С1

ε-1(

 

 

ε9

1

ε2

 

)=

ε11

D1

ε-5(

 

ε10

0

1

 

)=

1

0111 10

1

2

0

0

1

 

1

 

1

 

0

С2

ε-2(

 

 

 

1

ε2

ε3

)=

ε11

D2

ε-10(

 

 

0

1

ε5

)=

1

0111 10

2

3

0

0

0

 

1

 

1

 

1

С3

ε-3(

 

 

 

 

ε2

ε3

ε4)=

ε9

D3

1(

 

 

 

1

ε5

ε10)=

0

0101 00

1

4

0

0

0

 

0

 

1

 

1

С4

ε-4(

 

 

 

 

 

ε3

ε4)=

ε3

D4

ε-5(

 

 

 

 

ε5

ε10)=

ε10 = µ2

0001 11

1

5

1

0

0

 

0

 

0

 

1

С5

ε-5(

 

ε5

 

 

 

 

ε4)=

ε3

D5

ε-10(

1

 

 

 

 

ε10)=

ε10 = µ2

0001 11

2

6

0

1

0

 

0

 

0

 

0

С6

ε-6(

 

 

ε9

 

 

 

)=

ε3

D6

1(

 

ε10

 

 

 

)=

ε10 = µ2

0001 11

3

7

1

0

1

 

0

 

0

 

0

С7

ε-7(

 

ε5

 

1

 

 

)=

ε3

D7

ε-5(

1

 

0

 

 

)=

ε10 = µ2

0001 11

4

8

0

1

0

 

1

 

0

 

0

С8

ε-8(

 

 

ε9

 

ε2

 

)=

ε3

D8

ε-10(

 

ε10

 

1

 

)=

ε10 = µ2

0001 11

5

9

1

0

1

 

0

 

1

 

0

С9

ε-9(

 

ε5

 

1

 

ε3

)=

ε3

D9

1(

1

 

0

 

ε5

)=

ε10 = µ2

0001 11

6

10

 

0

1

0

 

1

 

0

 

1

С10

ε-10(

 

 

ε9

 

ε2

 

ε4)=

ε3

D10

ε-5(

 

ε10

 

1

 

ε10)=

ε10 = µ2

0001 11

7

11

 

0

 

0

1

 

0

 

1

 

0

С11

ε-11(

 

 

 

1

 

ε3

)=

ε3

D11

ε-10(

 

 

0

 

ε5

)=

ε10 = µ2

0001 11

8

12

 

0

 

0

 

0

 

1

 

0

 

1

С12

ε-12(

 

 

 

 

ε2

 

ε4)=

ε13

D12

1(

 

 

 

1

 

ε10)=

ε5 = µ

1011 01

2

13

 

1

 

0

 

0

 

 

0

 

1

 

0

С13

ε-13(

 

ε5

 

 

 

ε3

)=

ε13

D13

ε-5(

1

 

 

 

ε5

)=

ε5 = µ

1011 01

3

14

 

1

 

1

 

0

 

 

0

 

 

0

 

1

С14

ε-14(

 

ε5

ε9

 

 

 

ε4)=

ε13

D14

ε-10(

1

ε10

 

 

 

ε10)=

ε5 = µ

1011 01

4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

9

3. Декодирование с гарантийно неисправляемой ошибкой.

Для декодирования последовательности внесём соответствующие ошибки в последовательность, определённые вариантом задания. Многочлен 11 + 9 + 7 определяет ошибки в принятой комбинации.

Выполним декодирование последовательности 2( ) = ( ) + 2( ), где f(x) – гарантийно неисправляемый кол БЧХЭ (15,6), сформированная в кодирующем устройстве. Операция внесения ошибки в исходную последовательность:

( ) = 1010100001101002( ) = 11 + 9 + 7

2( ) = 101010010010100

Процесс декодирования отображён в табл. 6.

Согласно процессу декодирования, отображённому в табл. 6 и принципу мажоритарного декодирования, было выявлена декодированная последовательность (C, D) = (1111 01), которая повторялась 6 раз, при чём данная последовательность не удовлетворяет исходной последовательности, следовательно, можно сделать вывод, что декодер не смог справиться с исправлением данного кода (15,6) равно 6 и код способен гарантийно исправить только все однократные и двухкратные ошибки.

Рисунок 5. Результат программной модели декодера.

10