Министерство образования и науки РФ

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

Кафедра «Автоматика и телемеханика»

Контрольная работа «Теория электрической связи»

Часть 2

Построение групповых систематических кодов.

Вариант 16

Выполнил студент группы ТКз-08-01

Промтов Александр Юрьевич Проверил доцент кафедры АТ

Фрейман Владимир Исаакович

Пермь, 2011г.

Содержание:

I. Техническое задание.	3
II. Краткое описание теории.	4
III. Расчетно-графическая часть контрольной работы:
1. Определение длины информационной части.	7
2. Расчет параметров избыточного кода.	7
3. Расчет операторов кодирования.	8
4. Построение кодера.	9
5. Декодирование группового систематического кода.	9
6. Построение декодера.	12
IV. Выводы о проделанной работе.	13
V. Список использованной литературы.	14

I. Техническое задание.

• Количество рабочих комбинаций кода: M_р=10.

• Способ задания кода: с помощью проверочной матрицы H.

• Значение информационной части: U=(16 mod 7)+1=2+1=3.

• Вариант реализации кодера ГСК: последовательный.

• Вариант реализации декодера ГСК: последовательный.

• Вид матрицы Р:

• Вероятность ошибки в одном символе: Р=10^-3.

• Допустимое значение вероятности трансформации: Р_тр.доп.=10^-6.

II. Краткое описание теории.

При избыточном кодировании информационного сообщения, длиной mсимволов, в него вводят дополнительные (избыточные)k символов. При этом общая длина передаваемого сообщенияnвычисляется по формуле:

[1]

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

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

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

Расстояние Хэмминга d_ijпоказывает степень различия между i-й и j-и кодовыми комбинациями. Равно числу несовпадающих в них разрядов.Математически расстояние Хэмминга вычисляется как число единиц в сумме по модулю два () этих кодовых комбинаций, что представляет собой вес кодовой комбинации их суммы W.

Минимальное кодовое расстояние d_min– это минимальное расстояние Хэмминга из всех вычисленных d_ij для возможных пар разрешенных кодовых комбинаций.

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

На этой схеме первичный код U, содержащийmинформационных символов, поступает на вход кодера, где к нему добавляютkизбыточных символов, рассчитанных особым образом. На выходе кодер появляется кодовый векторV, содержащийn = m+kсимволов. В последующих операциях передачи этого кодового вектора на него воздействуют помехиe, в результате чего на приемной стороне на вход декодера поступает уже измененный помехами кодовый векторV^’ = V  e. В декодере происходит обнаружение и исправление ошибочных символов, что возможно благодаря введенным избыточным символам.

При этом возможны три состояния приема сообщения:

• правильная передача – отсутствие ошибок или исправление ошибок;

• стирание – обнаружение ошибки и удаление сообщения;

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

Декодирование с обнаружением ошибок.

Для обнаружения ошибок кратности r кодовое расстояние d_min должно быть хотя бы на единицу больше r:

d_min ≥ r + 1

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

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

d_min ≥ 2s + 1

Декодирование с исправлением и обнаружением ошибок.

Для того чтобы избыточный код исправлял ошибки кратностью не более s и обнаруживал ошибки кратностью не более r (r > s), минимальное кодовое расстояние должно определиться по формуле:

d_min ≥ s + r + 1

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

Для кода, исправляющего ошибки кратности не более s (при вероятности ошибки в одном символе P):

[2]

Для кода, исправляющего ошибки кратности не более s и обнаруживающего ошибки кратностью не более r (r > s):

[3]

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

Чтобы определить, сколько избыточных символов k = ( n–m ) надо ввести в сообщение для возможности кода исправить ошибки максимальной кратностью s, существует определение верхней границы Хэмминга для двоичных кодов:

[4]

Подставляя в неравенство известное значение информационных символов m и требуемое значение кратности s, добиваются, путем подбора n, его выполнения.

Построение групповых систематических кодов.

Вектор ГСК имеет вид V=( a₁,a₂,…,a_m,c₁,c₂,…,c_k), гдеc₁,c₂,…,c_k – добавочные избыточные символы, которые находятся по формуле:

[5]

Множитель p_ij – элемент кодирующей матрицы P размерности [m x k].

Для перехода к коду с четным d_min (к коду, исправляющему ошибку кратности s и обнаруживающему ошибку кратности r = s+1) используются формулы перехода:

d_{min чет}= d_{min нечет} + 1

k_чет = k_нечет + 1

n_чет = n_нечет + 1

m = const

К кодовой комбинации добавляется дополнительный избыточный символ, который вычисляется по формуле:

[6]

Такая процедура формирования кода выполняется только для кодов Хэмминга (s = 1, d_min = 3 или s = 1, r = 2, d_min = 4).

Декодирование групповых систематических кодов.

Вектор ГСК на входе декодера имеет вид V^’ = V  e, т.е. измененный под воздействием ошибок по отношению к исходному векторуV.

Для декодирования ГСК применяется принцип синдромного декодирования. Синдром группового кода вычисляется по формуле:

[7]

Множитель – элемент транспонированной проверочной матрицы H, имеющей размерность [k x n]. Проверочная матрица H_kxn в каноническом виде определяется, как:

[8]

где I_k – единичная матрица размерности [k x k], P^T – транспонированная кодирующая матрица P размерности [k x m].

Для кодов с четным d_minпоследний (k+1)-й разряд вектора синдрома, согласно общей проверке на четность, находится по формуле:

[9]

После вычисления синдрома составляется таблица истинности, согласно которой происходит декодирование с исправлением и обнаружением ошибок:

№ п/п	S1, S2,…,Sk	Sk+1	Кратность ошибок в векторе V′
1	0	0	Ошибок нет
2	≠0	1	Ошибки нечетной кратности, в частности однократная ошибка
3	0	1	Ошибки в символе ck+1
4	≠0	0	Ошибки четной кратности, в частности двукратная ошибка

Ошибка в пункте 2 таблицы находится в разряде, который входит во все координаты синдрома, равные 1, и не входит в координаты синдрома, равные0. В пунктах 2 и 3 происходит исправление ошибки, а в пункте 4 – стирание сообщения. При ошибках кратностью большеrпроисходит трансформация сообщения.

III. Расчетно-графическая часть контрольной работы.