Математические модели процессов обработки данных (курсовая) Охорзин
.pdfФЕДЕРАЛЬНОЕ АГЕНСТВО СВЯЗИ ФЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«Санкт-Петербургский государственный университет телекоммуникаций им. Проф. М. А. Бонч-Бруевича»
Кафедра «Сетей связи и передачи данных (СС и ПД)»
Курсовой работа по дисциплине: «Математические модели процессов обработки данных»
ИССЛЕДОВАНИЕ ПРИНЦИПОВ КОДИРОВАНИЯ И ДЕКОДИРОВАЯ КОДОВ БЧХЭ
Выполнил: Вариант 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