Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf

Скачать файл (8,51Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.10.2024

Просмотров: 183

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

При этом кодируемые числа не Должны превышать величины (2е12—1)/А. Но число 2е1г—1 на Л не делится и ближайшее целое число, которое делится на А и не

превышает	2е / 2 —-1,		равно 2 е / 2 + 1 — А . Отсюда				получаем,
что
Ы0=		(U"i2+1 — А)/А			= (2<V2 +1 )1А—1.
Тем самым первая часть теоремы доказана.
Если не существует х , удовлетворяющего							сравнению
(5-4), то п	=	е ,	и максимальное			значение	кодируемого
числа			N0={2r—		1)/Л — 1.
			N0={2r—		1)/Л — 1.
Единица	вычитается			для	того,	чтобы максимальное
значение кодового			слова	не	могло	достигнуть	величины

2"—1 = 111...1. Если бы число 111...1 было кодовым словом, то ошибка —1 в младшем разряде перевела бы его в число 00...О, которое соответствует кодовому представлению числа УУ = 0.

Покажем, что, в частности, сравнение (5-4) невоз можно, если е — нечетное число. Действительно, при нечетном е равенство (5-5) удовлетворяется только в том случае, когда b четно, т. е. равно 2, 4, 6, ... Тогда х

принимает значения е, 2е, Зе, ..., при		которых,	как это
следует из определения порядка,	справедливо сравнение
2 * = 2 i e = l по модулю Л	(i = l,	2, 3, . . . ) ,

что противоречит сравнению (5-4). Теорема доказана полностью.

Для синтеза ЛУУ-кодов в соответствии с теоремой 5-2 можно пользоваться табл. 5-2, в которой приведены по-

									Т а б л и ц а		5-2
е	Значения		А	с		Значения А			е	Значения А
2	3			12	13,	35,	39,	45	36	37,	95
3	7				65,	91			39	79
4	5,	15		14	43				48	97
5	31	21,	63	18	19,	27,	57	75	52	53
6	9,	21,	63	20	25,	41,	55,	75	54	81
7	127			21	49				58	59
8	17,	51,	85	22	69				60	61
9	73			23	47				66	67
9	73	33,	93	28	29,	87			66	67
10	11,	33,	93	30	77,	99			82	83
11	23,	89		35	71				100	101
9*											131

						Т а б л и ц а	5-3
			Максимальное		значение	Количество
Длина	Порождающий		кодируемого		числа	информацион
кода л	модуль А		л,	2 " - '		ных разрядов
			л,	2 " - '		ft=loga	No
			Л'„=	А		ft=loga	No
9	19				26	4
10	25				40	5
11	23				88	в
14	29				564	9
18	37				7 084	12
21	49			42 798		15
23	47			178 480		17
26	53			1 266 204		20
29	59			9 099 506		23
30	61		17 602 324			24
33	67		128 207 978			26
35	7 1	-	483 939 976			28
39	79		6 958 934 352			32
41	83		26 494 256 090			34
50	101		5 099 523 830 124			43

рядки е класса вычетов 2 по нечетным модулям /4^101 . В табл. 5-3 приведены параметры ЛЛ^-кодов, порождае мых нечетными модулями A<g: 101.

Т а б л и ц а 5-4

Максимальное					Количество
значение	ЛЛ'+В-код			Длина кода л	информацион
кодируемого	ЛЛ'+В-код			Длина кода л	ных разрядов
числа Wo					k
7	I 9 J V + 6 1 .	23/V+47,		8	3
	25ЛЧ-40, 27ЛЧ-33,
	29ЛЦ-26,	35W+5
15	19//+113,	23iV+83,		9	4
	25ЛЦ-68,	27/V+53,
31	29W+38			10	5
31	23ЛЧ-155, 25ЛЦ-124,			10	5
63	29ЛЧ-62			11	6
63	23W+279,	29N+110		11	6
127	29ЛГ+206			12	7
255	29W+398			13	8
511	29JV+782			14	9
1 023	37ЛЧ-13 842.		47W+8 727,	16	10
	49ЛЧ-7 704,		53iV+5'658,
	55iV+4 630,		59^+ 2 645,
	6 Ш + 1 5 6 6

132

В табл.	5-4	приведены		параметры некоторых
AN + Б-кодов	с исправлением			одиночной ошибки, най
денных Брауном [Л. 40].
Рассмотренные AN-			и ЛУУ + В-коды		являются	нераз
делимыми, так как		в	кодовых	словах	нельзя	указать

позиции информационных и контрольных разрядов. Однако Л/У-коды можно привести к форме разделимых,

если кодирование числа N	производить	в	соответствии
со сравнением
2rN -\-C(N)s=Q	по модулю	А,	(5-6)

где г — количество двоичных разрядов, необходимое для записи контрольных кодов C(N). Контрольные коды C(N) вычисляются следующим образом:

С(Д/)= — 2rN по модулю А,

т. е. O^C(N) <:А и r—[logzA]. Умножение числа iV ввыражении (5-6) на 2Г «смещает» информационные разря ды влево на г разрядов, и «освободившиеся» г разрядов

используются для записи контрольного кода		C(N). Для
того чтобы приведение ЛЛ^-кода	к форме	разделимого
не нарушало корректирующих	свойств кода, синтези

руемого в соответствии с теоремой 5-2, кодируемые чис ла должны удовлетворять неравенству

		2п— 1 > 2 Г Л / + 2 Г — 1,
т.	е. максимальное значение кодируемого числа			No =
= 2n~r— 1.
	5-2. АРИФМЕТИЧЕСКИЕ Р А З Д Е Л И М Ы Е КОДЫ,
	П О Р О Ж Д А Е М Ы Е НЕСКОЛЬКИМИ МОДУЛЯМИ
	Кодовое слово арифметического разделимого кода
длиной п разрядов состоит из k			информационных	раз
рядов и п—k		контрольных. Такой	код будет обозначать
ся	через (л,	k). Содержимое п—k	контрольных разря

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

133

Пусть код порождается одним модулем А: Тогда требуемое количество двоичных контрольных разрядов

n—k=[\og2A\.

Например, если /1 = 11, то	п—/e=[log2	11]=4 разрядам.	Действи
тельно, максимальное значение	остатка	при делении на 11	равно 10

и двоичное представление этого числа содержит четыре разряда.

Количество информационных разрядов k может быть		произвольным,
и длина кода равна:
rt=fc+[log2	Л].разрядов.
Пусть в информационных	разрядах записано число В,
а в контрольных — число \|3, т. е.
B=gA	+ $,	(5-7)

где g — целая часть частного от деления числа В на мо дуль, |3 — остаток. Выражение (5-7) можно переписать следующим образом:

В— р = ё Л

или
В — р = 0 по модулю А.	(5-8)

Согласно (5-8) я-разрядная двоичная последователь ность является кодовым словом, если разность между

информационной и контрольной частями

слова сравнима

с нулем по модулю А.

Код, порождаемый модулем А, позволяет обнаружить

любую

одиночную

ошибку

вида ± 2 ' ,

если

± 2 * ^ 0

по модулю А при

— 1 ;

в этом

случае В—^+ЕгФО

по

модулю

А.

Таким

обра

зом, если в качестве

выбрать

любое

число,

не

равное

степени

двойки

(3,

10,

И и т. д.),

то 2*Ф0 по

модулю

А и порождаемый

код

позволяет

обнаружить

любую

одиночную

ошибку.

Простейший

код,

порождае

мый модулем А = 3,

содержит

два

контрольных разряда.

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

Вычислим вероятность пропуска двойной ошибки для заданного модуля А (вероятностью возникновения оши бок одновременно в информационной и контрольной ча-

134

стях слова пренебрегаем). Ошибка кратности два не бу дет обнаружена, если

±2 г " rb 2J' = 0 по модулю А, где
или если i>j, то
(2'~' zh 1) = 0 по модулю А.		(5-9)
Так как 2 ^ 0	по модулю А, то сравнение	(5-9) мо
жет иметь место только в том случае, если
2'zirl=^ 0 по модулю А
или	г = :±;1 по модулю А,
2	г = :±;1 по модулю А,

где 2s^/s^i— 1.

Если ошибки равновероятны, то вероятность пропуска

ошибки кратности два равна:
Q2 = 0,5Ai + 0,5Я2 =0,5 (A*+ta),	(5-10)

где Ki — вероятность выполнения сравнения 2 ' = 1 по мо дулю A; %z — вероятность выполнения сравнения 2 ' =

==— 1=Л — 1 по модулю А. Если порядок 2 по модулю

Аравен е, то

Сравнение	2 ' = — 1 по			модулю А возможно только
в том случае,	если		е — четное число		(см. доказательст
во теоремы 5-2). Поэтому
	f 1/е,		если	е — четное	число;
2	1 0,		если	е — нечетное число.
Например, пусть /4=3. Из				табл. 5-2 находим,		что е = 2 . Тогда
из выражения (5-10)		получаем:
			Q2 =0,5(0,5+0,5) =0,5,
т. е. арифметический		разделимый код, порождаемый				модулем Л = 3 ,

не обнаруживает 50% ошибок кратности 2. Аналогично, если Л = 7 , то е = 3 и

Q2 =0,5(l/3+0) = 1/6=0,17,

т. е. 17%' ошибок кратности 2 не обнаруживается кодом, порождае мым модулем Л = 7.

Для расчета вероятности пропуска ошибок произ вольной кратности можно использовать формулы, при веденные в табл. 5-5 [Л. 41].

135

Смотрите также файлы

Шахнович, А. Р. Математические методы в исследовании биологических систем регулирования.pdf

Швырков, В. В. Моделирование внутригодичных колебаний спроса.pdf

Шелепин, О. Е. Химия перициклических соединений.pdf

Шнепс, М. А. Численные методы теории телетрафика.pdf

Щербаков, Р. Н. Основы метода внешних форм и линейчатой дифференциальной геометрии.pdf

Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf

Смотрите также файлы

Информация

Списки файлов

Дополнительно