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

Тип работы:
Реферат
Предмет:
Геолого-минералогические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Проектирование и тестирование логических устройств
УДК 004. 052. 32:519. 72
Т. Х. Черкасова, канд. физ. -мат. наук
Кафедра «Компьютерные информационные технологии», Санкт-Петербургский политехнический университет Петра Великого
ОБНАРУЖЕНИЕ ОШИБОК В СИСТЕМАХ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ С ПОМОЩЬЮ КОДОВ БЕРГЕРА
И ЕГО МОДИФИКАЦИЙ
Введение
В данной работе рассматриваются коды Бергера [1]. Из современных публикаций на эту тему [2−4] можно сделать выводы о том, что использование таких кодов актуально, ведутся исследования по их модификациям. Получены некоторые удобные формулы для классического кода Бергера и предложена некоторая его модификация, которая названа комбинированным кодом Бергера [5].
Коды Бергера используются в схемах встроенного контроля. Это нелинейные равномерные двоичные коды, к m информационным разрядам которого добавляются k контрольных разрядов, содержащих двоичное число единиц в информационных разрядах. Число k = |~log2 (m +1)~| - целое сверху числа log2 (m +1). Как известно, код Бергера обнаруживает
любое нечетное количество ошибок. Он не обнаруживает ошибки четной кратностью, когда, например, две единицы преобразовались в нули, а два нуля в единицы.
В работе предлагается комбинированный код Бергера с проверкой на четность.
1. Комбинированный код Бергера
Пусть длина информационной части кода равна m. Тогда по правилу Бергера контролируем (m — 1) информационных разрядов, а m-й информационный разряд контролируем на четность вместе с первыми информационными разрядами. Кодовое слово а1а2 «. аm_1amаm+1 «. аm+kаm+k+1, первые m разрядов информационные, следующие k + 1 разрядов — контрольные, причем первые k контрольных разрядов организованы как в коде Бергера для m — 1 первых информационных разрядов — это двоичное число единиц в m — 1 разрядах, а k + 1-й контрольный разряд содержит сумму всех m информационных разрядов по модулю 2: аk+1 =а1 +а2 +… + аот mod2. Схема организации комбинированного кода
167
Проблемы безопасности и надежности микропроцессорных комплексов
am+1--am+k (а1 +***+am-1)2
ttm ага-1ага-2 -а2 °Ч
«m+k+1 ="1 +•••+ «m mod 2
Если в контролируемом слове комбинированного кода Бергера m информационных разрядов, то в кодовом слове будет такое же количество разрядов, как и в обычном коде Бергера, или на один больше.
Для примера получим значения разрядов вектора комбинированного кода Бергера для информационного слова х = 0110. Кодовое слово кода Бергера будет yB = 110 010. Здесь 3 контрольных разряда, в трех разрядах записано число 2 — количество информационных единиц. Всего отведено 3 контрольных разряда, так как наибольшее количество информационных единиц всего 4, число 4 в двоичной записи 100 занимает 3 разряда. Комбинированный код Бергера yK = 110 100.
По аналогии заполняются три контрольных разряда: в первых двух записывается количество единиц в старших разрядах, третий контрольный разряд содержит сумму всех четырех информационных разрядов по модулю 2, включая младший информационный разряд. Как известно, код Бергера обнаруживает любое нечетное количество ошибок. Предложенный комбинированный код Бергера тоже обнаруживает нечетное количество ошибок. Если нечетное количество ошибок в первых m — 1 информационных символах, то они обнаружатся кодом Бергера для этих разрядов- нечетное количество ошибок может быть таковым, что будет четным количество ошибок в первых m — 1 разрядах, а так произойдет одна ошибка в младшем разряде, но при проверке на четность такое искажение тоже обнаружится. Как и для обычных кодов Бергера, найдем необнаруживаемые ошибки четной кратностью d, но только в (m — 1) разрядах. В [2−4] показано, что для m информационных разрядов общее количество ошибок в информационных разрядах
(d
m,(m-1) m 2 d d
(1)
где d = 2,4,…, m, если m — четное, d = 2,4,…, m -1, если m — нечетное.
Количество необнаруживаемых искажений кратностью d [2]
d
2^-d C^dC 2
(2)
168
Проектирование и тестирование логических устройств
Если обозначить через m количество информационных разрядов, то количество необнаруживаемых ошибок кратностью d в m — 1 информационных разрядах
d
Nm-I, d = cm _iCd22m-1-d. (3)
Количество необнаруживаемых ошибок кратностью d в комбинированном коде Бергера, имеющем m информационных разрядов, будет
d
NKm, d = 2Nm_i, d = cm_c 2m-d. (4)
Это объясняется тем, что каждая из ошибок в m — 1 разряде кода может появиться при значении младшего разряда, равном единице или нулю. Общее количество необнаруживаемых ошибок в m информационных разрядах комбинированного кода
NKm
m-1,(m-2) f
= I
d=2 ^
d
Cm-1Cd
22
m-d
(5)
2. Необнаруживаемые ошибки в комбинированных кодах Бергера
В работе [2] доказана теорема, утверждающая, что доля необнаруживаемых ошибок кратностью d в информационных разрядах от общего числа ошибок информационных разрядов данной кратностью не зависит от числа информационных разрядов и является постоянной величиной:
d
Pd = 2-dC2. (6)
Относительное количество необнаруживаемых ошибок кратностью d для комбинированного кода Бергера:
Pd, m
NK
m, d
2 NK
m-1,d
2 mC
2 mC
d
d
где NKm d = 2NKm-1 d = Cj C& lt-m-12m-d — число необнаруживаемых ошибок
кратностью d в m — 1 информационных разрядах, в знаменателе — общее количество возможных ошибок в m разрядах.
Тогда доля необнаруживаемых ошибок кратностью d в m разрядах комбинированного кода Бергера
P =-2
Pd, m Z
d
— d гч 2 d
c
(7)
m
169
Проблемы безопасности и надежности микропроцессорных комплексов
Сравним этот коэффициент с коэффициентом обычного кода Бергера
fid • Видн°, что fid, m =fid
(d Л 1 — d
V m)
Доля необнаруживаемых ошибок крат-
ностью d в m разрядах для комбинированного кода Бергера меньше такой же доли для обычного кода Бергера. Коэффициент fid m показывает, что в
комбинированных кодах обнаруживаются все ошибки кратностью m. Для нечетных m это происходит из-за общей проверки на четность, при четных m в контролируемых по Бергеру (m — 1) разрядах m -1 — нечетное число ошибок, они обнаруживаются по правилу кода Бергера для m — 1 разрядов.
В классическом коде Бергера могут быть только ошибки четной кратностью. Вычислим количество всех необнаруживаемых ошибок в m информационных разрядах. Для четного числа m ошибки могут быть кратностью 2, 4, …, m — 2, m. Общее количество необнаруживаемых ошибок
m
m 2
NAm = X Nd = ECm& quot-C2k 2m-2k.
d=2& quot- ,& quot-=1 & quot-=1
Комбинаторную сумму в последней формуле можно вычислить. Для этого воспользуемся известной суммой [6]:
h
V '-s-ih+k 2k л 2k /~2h /оч
X Уп Ch+k4 = C2n. (8)
k=0
m
Преобразуем выражение для NAm. В сумме сделаем замену j = - - & quot-.
m 1 ~2
Тогда NAm = Xp2 2jCm-2,-4j, так как 1 & lt- k & lt- Z, то 1 & lt- j & lt- - -1,2& quot- =
2 2
m
j=o
= m — 2 j. Преобразуем выражение для NAm, чтобы свести к известной
m --
сумме (8): NAm ^C^C^4j — C
j=0
_m mm m m-2--------
2 C 2 2 42
m ^ _m
m-2-
2
Преобразуем также выражение под знаком суммы:
m! (m — 2 j)!
m
im-2j 2 J
Cm-2 jC
m-2 j
(m — 2j)!(2j)! (m
m
j n T-j
л
)
170
Проектирование и тестирование логических устройств
m!
(m У, У — + J
m
7 — J
v2 у
V
J
m
cj+J cm
7+J
m
m
2 m m 2 m
Получим NAm =ttjcm 4 — cm C042 = $cfJC2J + - 2m.
j=0 2+J j =0 2+
В выражении для NAm первое слагаемое со знаком суммирования — это
% ч 1 j 2 '- '- 2
известная сумма, где n = m, h = -, поэтому? cj cj 4J = c2j = c
2 j=0 T+j '-
m -+J
2 m
m 2 m
Значит,
na,=cm
(9)
Для нечетных m приведенная формула также справедлива, но непосредственно из формулы (3) ее трудно вывести. В этом случае следуем преобразованиям, предложенным в работах [7, 8]. Это метод формальных степенных рядов. И для общего количества необнаруживаемых ошибок четной кратностью в нечетном количестве информационных разрядов получим
m-1
m-1 2
NAm =? N = ?c2mkc2_t 2m-2k, NAm = cjm — 2m.
d=2k, k=1 k=1
Итак, имеем простые формулы для вычисления общего числа ошибок в информационных разрядах кода Бергера. Применение формулы, аналогичной формуле (9), позволяет вычислить количество ошибок в комбинированном коде Бергера. Для комбинированного кода Бергера, имеющего m информационных разрядов, количество необнаруживаемых ошибок четной кратностью в два раза больше количества необнаруживаемых ошибок четной кратностью для обычного кода Бергера с m — 1 информационным разрядом:
NKm = 2NA,-, = 2(cj2 -2m-1) = 2c2m"-2 -2m. (10)
Предел отношения количества ошибок для сравниваемых кодов
k = lim
m^-ro
m r*m
lim---------
m^ro 2 cm -2m
2m-2 ^
= 2.
(11)
171
Проблемы безопасности и надежности микропроцессорных комплексов
Заключение
Итак, для большого количества информационных разрядов общее число необнаруживаемых ошибок для комбинированного кода Бергера в два раза меньше общего числа необнаруживаемых ошибок для обычного кода Бергера. Возможны и другие модификации кода [5, 6], для которого общее число необнаруживаемых ошибок будет таким же, как и для приведенной модификации, но их распределение по кратностям будет иным.
Библиографический список
1. Berger J. M. А Note on Error Detecting Codes for Asymmetric Channels / J. M. Berger // Information and Control. — 1961. — Vol. 4. — Issue 1. — Pp. 68−73.
2. Ефанов Д. В. Три теоремы о кодах Бергера в схемах встроенного контроля / Д. В. Ефанов // Информатика и системы управления. — 2013. — № 1. — С. 77−86.
3. Ефанов Д. В. О свойствах кода с суммированием в схемах функционального контроля / Д. В. Ефанов, Вал. В. Сапожников, Вл. В. Сапожников / Автоматика и телемеханика. — 2010. — № 6. — С. 155−162.
4. Сапожников Вал. В. Предельные свойства кода с суммированием / Вал. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов // Известия университета путей сообщения. — 2010. -№ 3. — С. 290−299.
5. Грабко И. О. Комбинированный код Бергера / И. О. Грабко, Т. Х. Черкасова // Неделя науки СПбГПУ: материалы Научно-практической конференции с международным участием — Институт информационных технологий и управления СПбГПУ. — СПб.: Изд-во Политехнического ун-та, 2014. — С. 253−255.
6. Грабко И. О. Коды с суммированием и их модификации в функциональных системах контроля / И. О. Грабко, Т. Х. Черкасова // 68-я региональная научно-техническая конференция студентов, аспирантов и молодых ученых «Студенческая весна-2014»: сб. научных статей [Электронный ресурс]. — С. 162−166.
7. Леонтьев В. К. Избранные задачи комбинаторного анализа / В. К. Леонтьев. — М.: Издательство МГТУ им. Н. Э. Баумана, 2001. — 184 с.
8. Егорычев Г. П. Комбинаторные суммы и метод производящих функций / Г. П. Его-рычев. — Красноярск: Изд-во Красноярского гос. ун-та, 1974. — 200 с.
Email: cherkasova-tnz@vandex. ru
172

ПоказатьСвернуть
Заполнить форму текущей работой