Конспект ТЭС 2 сем

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

4 ЦИКЛИЧЕСКИЕ КОДЫ

4.1 Основные понятия

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

Циклические коды – линейные блочные коды, обладающие свойством циклич-

ности: если b = (bn−1bn−2 ...b1b0 ) - кодовое слово циклического кода, то его циклическая перестановка b'= (bn−2 ...b1b0bn−1 ) также является кодовым словом.

Пример 4.1:

b = (1001110) → b' = (0011101) → b'' = (0111010) .

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

Все преобразования кодовых слов циклических кодов производятся в виде математических операций над полиномами (многочленами). Для этого кодовые слова представляются в форме полиномов:

b(x) = bn−1 xn−1 +bn−2 xn−2 +... +b1 x +b0 ,

где bi ={0,1} - коэффициенты полинома;

x - символическая переменная. Пример 4.2:

b = (1001110) → b(x) =1 x6 + 0 x5 + 0 x4 +1 x3 +1 x2 +1 x1 +0 x0 = x6 + x3 + x2 + x .

Операции сложения, вычитания, умножения и деления полиномов выполняются по обычным арифметическим правилам, только вычитание заменяется сложением, которое производится как сложение по модулю два.

Циклические коды задаются с помощью порождающего (образующего) g(x) и проверочного h(x) полиномов.

Любой полином g(x) степени r = n −k , который делит без остатка полином вида xn +1, называется порождающим полиномом:

g(x) = gr xr + gr−1 xr−1 +... + g1 x + g0 ,

где gi ={0,1} - коэффициенты полинома.

Полиномы всех кодовых слов делятся без остатка на порождающий полином. Порождающая матрица строится на основе полинома g(x) .

Для несистематического циклического кода:

		0	...	0	gr	gr−1
G =		...	0	gr	gr−1 ...
		...	...	...	...	...
		gr	gr−1	...	g1	g0

Для систематического циклического кода:

G = Ik R ,

...	g1	g0
g1	g0	0		.
... ... ...
0 ...		0

11

где R - прямоугольная подматрица k ×r , строками которой являются коэффициенты полинома остатка от деления xn−i на полином g(x) , где i - номер строки.

Пример 4.3:
Показать, что			полином g(x) = x4 + x3 + x2 +1 является порождающим для 7-
разрядного циклического кода. Записать матрицу G .
	x7	+1		x4 + x3 + x2 +1
	x7	+ x6 + x5 + x3			x3 + x2 +1

x6 + x5 + x3 +1 x6 + x5 + x4 + x2

x4 + x3 + x2 +1 x4 + x3 + x2 +1

0

Для несистематического кода:

G =		0	0	1	1	1	0	1		.
		0	1	1	1	0	1	0
		1	1	1	0	1	0	0

Для систематического кода:

x6							x4 + x3 + x2 +1					x5		x4 + x3 + x2 +1
x6 + x5 + x4 + x2								x2 + x				x5 + x4	+ x3 + x	x +1
		x5 + x4 + x2										x4	+ x3 + x
		x5 + x4 + x3 + x										x4	+ x3 + x2 +1
				x3 + x2 + x →1110;									x2 + x	+1 → 0111;
x4							x4 + x3 + x2 +1
x4 + x3 + x2 +1						1
		x3 + x2 +1 →1101;
G =		1	0	0	1	1		1	0		.
		0	1	0	0	1		1	1
		0	0	1	1	1		0	1

Результат деления полинома вида xn +1 на порождающий полином называется

проверочным полиномом:

h(x) = (xn +1) / g(x) = hk xk + hk −1 xk −1 +... + h1 x + h0 ,

где hi ={0,1} - коэффициенты полинома.

При отсутствии ошибок в принятом кодовом слове b * остаток от деления произведения b * (x)h(x) на полином вида xn +1 равен нулю:

b * (x)h(x) mod(xn +1) = 0 .

Проверочная матрица строится на основе полинома h(x) . Для несистематического циклического кода:

		h0	h1	...	hk −1	hk	0	...	0
H	=	0	h0	h1 ...		hk −1 hk		0	...		.
		... ... ... ...				... ... ... ...
		0	...	0	h0	h1 ...		hk −1	hk

12

Для систематического циклического кода:

H = RT Ir .

ДОМАШНЕЕ ЗАДАНИЕ:

2. Найти полином h(x) для задачи из примера 4.3. Записать матрицу H .

4.2 Кодирование информации

Существует два способа кодирования:

- несистематическое кодирование:

b(x) = a(x)g(x) ,

где a(x) - полином информационного слова, b(x) - полином кодового слова;

- систематическое кодирование:

b(x) = a(x)xr + r(x) ,

где r(x) - остаток от деления произведения a(x)xr на полином g(x) . Пример 4.3:

Закодировать слово a = (010) циклическим кодом из примера 4.3. Несистематическое кодирование:

b(x) = a(x)g(x) = x(x4 + x3 + x2 +1) = x5 + x4 + x3 + x → b = (0111010) .

Систематическое кодирование:

1) a(x)xr = x x4 = x5 ;

	a(x)xr / g(x) = x5		x4 + x3 + x2 +1
	x5 + x4	+ x3 + x		x +1
2)	x4	+ x3 + x		;
	x4 + x3 + x2			+1
		x2 + x +1 = r(x)
3)	b(x) = a(x)xr + r(x) = x5 + x2 + x +1 →					= (0100111) .
					b

4.3 Кодирующие устройства

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

Правила построения схем умножения и деления:

- число ячеек памяти равно старшей степени полинома g(x) . Ячейка для старшей

степени отсутствует;

- число сумматоров на единицу меньше веса полинома g(x) : при умножении отбра-

сывается сумматор для младшей степени; при делении – для старшей. Сумматоры устанавливают перед ячейками памяти для соответствующих степеней; - при умножении множимое подается одновременно на вход и на все сумматоры,

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

13

a(x)

	g	gr-1	g
g0	1		r
	x1		xr-1
x0

1	2	r	a( x)b(x)

Рисунок 4.1 – Кодер несистематического циклического кода.

Кодер реализует алгоритм b(x) = a(x)g(x) . В течение первых k тактов на вход

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

К2 Вход

	g	gr-1
g0	1
	x1	xr-1
x0			1
				Выход
1	2	r	К1

Рисунок 4.2 – Кодер систематического циклического кода.

Кодер реализует алгоритм b(x) = a(x)xr + r(x) . Вначале ключ К1 находится в по-

ложении 1, а ключ K 2	замкнут. Информационные символы, подаваемые на вход,
через ключ К1 поступают на выход, а через ключ К2				- в кодирующее устройство,
где через k тактов образуется r проверочных символов,					представляющих собой
остаток от деления произведения a(x)xr		на полином g(x) . Затем ключ К1 переводит-
ся в положение 2, а ключ K 2 размыкается. Регистр делает r					тактов, выдавая прове-
рочные символы на выход.					2
Пример 4.4:
1 Построить схему кодера циклического кода из примера 4.3.
a(x)
g0	g2		g3		g4
x0	x1	x2		x3

1

2

3

4	a(x)b(x)

Рисунок 4.3 – Кодер несистематического кода.

2 Схему кодера систематического кода построить самостоятельно.

ДОМАШНЕЕ ЗАДАНИЕ: 1. [3.1.2] с.315…318; [3.1.3] с.200…204; [3.1.5] с.149…150;

[3.1.14] с.263…270, 282…286.

14

5 ДЕКОДИРОВАНИЕ ЛИНЕЙНЫХ КОДОВ

Существует три основных метода декодирования линейных кодов:

-декодирование по максимуму правдоподобия (по минимуму расстояния);

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

-декодирование по синдрому.

5.1 Декодирование по максимуму правдоподобия

Правило декодирования:

В качестве переданного слова b следует выбирать слово, которое ближе всего по Хэммингу к принятому b *.

b*	УСр 1

	УСр 2	b
		РУ
		УСр М
b1	b2	bM

ГКС

Рисунок 5.1 – Структурная схема декодера по минимуму расстояния.

На рисунке: УСр – устройство сравнения; ГКС – генератор кодовых слов; РУ – решающее устройство.

Данный метод используется, когда число информационных символов k мало

( r >> k ).

5.2 Мажоритарное декодирование

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

Существует три способа построения систем проверочных уравнений для декодирования символа:

-системы с разделенными проверками – символ, относительно которого разделяется система, входит во все уравнения. Любой другой символ входит не более, чем в одно уравнение. Для коррекции t ошибок необходимо 2t +1 уравнений в системе;

-системы с λ -связанными проверками – символ, относительно которого разрешается система, входит во все уравнения. Любой другой символ входит не более, чем в λ

уравнений. Для коррекции t ошибок необходимо 2λt +1 уравнений в системе;

- системы с квазиразделенными проверками – система разделима относительно некоторой суммы символов. На первом этапе она разрешается относительно суммы символов, а на втором – относительно конкретного символа.

15

b*=(b 1*b2*…bn *)

a1

1 МЭ

ak

k МЭ

Рисунок 5.2 – Структурная схема мажоритарного декодера.

На рисунке: 1…k – устройства, реализующие проверки для соответствующей системы; МЭ – мажоритарный элемент, принимающий решение о значении символа по большинству результатов проверок.

Пример 5.1:

Код (8,4) задан матрицей:

	1	1	0	0	1	0	0	0
H =	0	1	1	0	0	1	0	0		.
	0	0	1	1	0	0	1	0
	1	0	0	1	0	0	0	1

Система уравнений по матрице Н:

b1 +b2 +b5 = 0,b2 +b3 +b6 = 0,b3 +b4 +b7 = 0,

b1 +b4 +b8 = 0.

Система проверочных уравнений для a1 :

a1 = b2 * +b5 *,a1 = b4 * +b8 *,a1 = b1 *.

Система проверочных уравнений для a2 :

a2 = b1 * +b5 *,a2 = b3 * +b6 *,a2 = b2 *.

Система проверочных уравнений для a3 :

a3 = b2 * +b6 *,a3 = b4 * +b7 *,a3 = b3 *.

Система проверочных уравнений для a4 :

a4 = b3 * +b7 *,a4 = b1 * +b8 *,a4 = b4 *.

Пусть b * = (10110000) .

16

a = 0 + 0 = 0,			a	2	=1+0 =1,		a	3	= 0 +0 = 0,
1		=1;			=1+0 =1, a2	=1;			=1+0 =1, a3 =1;
a1 =1+0 =1, a1			a2				a3
a =1.			a	2	= 0.		a	3	=1.
1
a4	=1+ 0 =1,
	=1+0 =1, a4	=1.
a4
	=1.
a4

Результат декодирования: a = (a1a2 a3a4 ) = (1111) .

5.3 Декодирование по синдрому

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

принятому кодовое слово. Она содержит N = 2r строк и M +1 = 2k +1 столбцов.
Таблица – Стандартная таблица.
s1=(0…0)	b1=(0…0)	b2	…	bM
r	n
s2	e2	b2+e2	…	bM+e2
…	…	…	…	…
sN	eN	b2+eN	…	bM+eN

bi – кодовые слова;

ej – векторы ошибок – образцы ошибок минимального веса; bi+ej – слова, не являющиеся кодовыми;

si=ei·HT – синдромы – векторы размерностью r, указывающие на наличие и расположение ошибок в принятом слове.

Правило декодирования:

1. Вычисляется синдром s по принятому слову b *:

s = b * H T .

Если s = 0 , то b * является кодовым словом. В противном случае (s ≠ 0 ) b * содержит ошибки.

2.По s находится наиболее правдоподобный вектор ошибки e .

3.Ближайшее к принятому кодовое слово b получается в результате суммирования

b * и e :

b = b * + e .

b*	s	e
БВС	С
	b*	b
	Б	К

Рисунок 5.3 – Структурная схема декодера по синдрому.

На рисунке: Б – буфер хранения принятого слова; БВС – блок вычисления синдрома; С – селектор (дешифратор) синдрома; К – корректор.

Данный метод используется, когда число проверочных символов r = n −k мало

(<10).

Пример:

Составить стандартную таблицу для систематического кода (5,2) с порождающей матрицей:

17

G =

1

0

1

0

1

.

0

1

0

1

1

Таблица

должна содержать N = 2r

= 25−2

= 8 строк и

M +1 = 2k +1 = 22 +1 = 5

столбцов.

Таблица – Стандартная таблица.

b1=(00000)

b2=(01011)

b3=(10101)

b4=(11110)

s1=(000)

e2=(00001)

b2+e2=(01010) b3+e2=(10100)

b4+e2=(11111) s2=e2·HT=(001)

e3=(00010)

b2+e3=(01001) b3+e3=(10111)

b4+e2=(11100) s3=e3∙HT=(010)

e4=(00100)

b2+e4=(01111) b3+e4=(10001)

b4+e2=(11010) s4=e4·HT=(100)

e5=(01000)

b2+e5=(00011) b3+e5=(11101)

b4+e2=(10110) s5=e5·HT=(011)

e6=(10000)

b2+e6=(11011) b3+e6=(00101)

b4+e2=(01110) s6=e6·HT=(101)

e7=(01100)

b2+e7=(00111) b3+e7=(11001)

b4+e2=(10010) s7=e7·HT=(111)

e8=(11000)

b2+e8=(10011)

b3+e8=(01101)

b4+e2=(00110)

s8=e8·HT=(110)

Пусть b * =(10111). Проведем декодирование.

1.s = b * H T = (010) ≠ 0 ;

2.e = (00010) ;

3.b = b * +e = (10101) .

ДОМАШНЕЕ ЗАДАНИЕ:

1.[3.1.2] с. 309…312, 317…318; [3.1.3] с. 205…208; [3.1.5] с. 147.. 149, 150…151;

[3.1.14] с. 258…261, 271…273.

2.Код (7,4) задан порождающей матрицей:

	1	0	0	0	1	1	1
G =	0	1	0	0	1	0	1	.
	0	0	1	0	0	1	1
	0	0	0	1	1	1	0

Провести декодирование по синдрому принятого слова b * = (1101101) .

6НЕПРЕРЫВНЫЕ (РЕКУРРЕНТНЫЕ) КОДЫ

6.1Общие сведения

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

Эти коды применяют для обнаружения и исправления пакетов ошибок. Пакет ошибок – ошибка, затрагивающая цепочку символов. Описывается длиной p и век-

тором ошибок e . Пример 6.1:

Пакеты ошибок длиной 4 могут быть такими:

e1 = (1001),e2 = (1101),e3 = (1011),e4 = (1111).

К непрерывным кодам относят цепной и сверточные. Цепной код является простейшим случаем сверточных.

18

6.2 цепной код

В таком коде после каждого информационного символа следует проверочный. Закодированная последовательность имеет вид:

a0b0,l a1b1,l+1...al bl,2l al+1bl+1,2l+1...,

где l - шаг сложения. Определяет корректирующие возможности кода; a0 a1...al al+1... - информационные символы;

b0,l b1,l+1...bl,2l bl+1,2l+1... - проверочные символы. Формируются по правилу: b0,l = a0 al ,

b1,l+1 = a1 al+1 ,

bl,2l = al a2l ,

bl+1,2l+1 = al+1 a2l+1 ,

Код позволяет исправить пачки ошибок длиной p ≤ 2l , если они разделены за-

щитным интервалом T ≥ 6l +1.

6.3 Сверточные коды (ск)

Это линейные, рекуррентные коды. Название обусловлено тем, что кодирование информации СК представляет собой операцию свертки двух функций:

k

bj (x) = ∑ai (x)gij (x),

i=1

где ai (x) - входная последовательность информационных символов; i =1,..., k - номер входа;

bj (x) - выходная последовательность кодовых символов;

j =1,..., n - номер выхода;

gij (x) = gij,0 + gij,1 x +... + gij,mi xmi - порождающий полином.

Набор порождающих полиномов определяет внутреннюю конструкцию кодера.

	1	Кодер СК	1
	2		2	bj(x)
ai(x)
		{gij(x)}
	k			n
Рисунок 6.1 – Обобщенная структурная схема кодера СК.
Кодирующее устройство содержит k		регистров сдвига и сумматоры по модулю

два. Количество двоичных разрядов i -ого регистра сдвига определяется старшей степенью полинома mi . Коэффициенты полинома gij,l ={0,1} определяют связи меж-

ду двоичными разрядами i -ого регистра сдвига и j -ым выходом кодера.

На практике чаще используются коды с единственным входным потоком (k =1) поэтому индекс i обычно опускается.

Пример 6.2:

19

Рисунок 6.2 – Структурная схема кодера несистематического СК с g1 (x) = x2 + x +1 и g2 (x) = x2 +1.

7 ГЕНЕРАТОРЫ С ВНЕШНИМ ВОЗБУЖДЕНИЕМ

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

7.1Классификация генераторов

1)По способу возбуждения различают генераторы с внешним возбуждением

(ГВВ) и автогенераторы (АГ).

ГВВ – устройство, работающее в вынужденном режиме, т.е. колебания на его выходе наблюдаются только при наличии колебаний от внешнего источника на его входе. ГВВ предназначены для усиления мощности, умножения частоты колебаний, осуществления АМ и ЧМ.

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

2)По форме генерируемых колебаний различают АГ гармонических и негармонических (релаксационных или импульсных) колебаний.

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

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

3)По частоте генерируемых колебаний различают инфранизкочастотные (менее 10 Гц), низкочастотные (от 10 Гц до 100 кГц), высокочастотные (от 100 кГц до 100 МГц) и сверхвысокочастотные (свыше 100 МГц) генераторы.

4)По выходной мощности различают маломощные (менее 1 Вт), средней мощности (ниже 100 Вт) и мощные (свыше 100 Вт) генераторы.

5)По типу используемых активных элементов различают генераторы ламповые, транзисторные, на операционных усилителях, на туннельных диодах, на динисторах.

6)По виду частотно-избирательной цепи различают генераторы LC -, RC - и

RL -типа.

7) По виду обратной связи различают генераторы с внутренней (с отрицательным сопротивлением) и с внешней (специально созданной) обратной связью.

20