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

. ':'< ш

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРОБЛЕД\ КИБЕРНЕТИКИ

На правах рукописи УДК 621.391.15

ДРОЖЖИ НА-ЛАБИНСКАЯ Анна Юрьевна

ПОСТРОЕНИЕ ПОКРЫВАЮЩИХ КОДОВ

И

ПРИМЕНЕНИЕ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ В СУПЕРЭВМ

Специальность 05.13.16 — применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТО РЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Л1осква 1992

Работа выполнена в Институте проблем кибернетики Российской Академии наук

Научный руководитель: доктор технических наук, профессор ¡0. Г. ДАДАЕВ

Научный к о н с у л ь т а н т: кандидат технических наук А. А. ДАВЫДОВ

Официальные оппоненты:

доктор физико-математических наук, профессор Э. М. ГАБИДУЛИН, кандидат физико-математических наук Г. А. ¡{АБАТЯНСКИЙ

Ведущая организация Институт проблем управления Российской Академии наук

Защита состоится „¿А" ^^-¿¿^Д/ 1992 г. в ^ часов на заседании специализированного совета Д.003.78.01 ИПК РАН по адресу: 117312 Москва, ул. Вавилова, 37.

С диссертацией можно ознакомиться в библиотеке Института.

специализированного совета ' ' >Л1 Ю. БЕЛЯЕВ

к. ф.-м. н.

Автореферат разослан " 1992 г.

Ученый секретарь

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Цель работы заключается в:

- решении дискретной экстремальной задачи построения двоичных линейных покрывающих кодов с малыми радиусами покрытия и плотностью покрытия близкой к минимальной;

- построении проверочных матриц и разработка алгоритма декодиро-

вания двоичных кодов Боуза-Чоудхури-Хоквингема (БЧХ) с шшималь-ным расстоянием 6, исправляющих двойные независимые ошибки и одиночные байты ошибок длины 4;

- разработке и реализации каскадного метода компактного тестирования конструктивных блоков суперЭВМ на основе кодов, локализующих ошибки.

Научная новизна работы состоит в следующем.

- Разработана модификация блочной конструкции проверочных матриц двоичных линейных покрывающих кодов с произвольными радиусами покрытия, предложенной А.А.Давыдовым. На ее основе построены бесконечные семейства кодов с малыми радиусами покрытия й = 2,э и 4. Покрытия, задаваемые этими кодами, лучше, чем покрытия известных кодов.

- Построены проверочные матрицы и разработан алгоритм декодирования двоичных кодов БЧХ с минимальным расстоянием б, способных наряду с исправлением двойных независимых ошибок исправлять одиночные байты ошибок длины 4 веса 4 и 3 и обнаруживать часть четырехкратных ошибок. Предполагается, что ошибки указанных типов не происходят одновременно. Приведены оценки обнаруживающей способности алгоритма декодирования.

- Для контроля и диагностики конструктивных блоков суперЭВМ разработан каскадный метод компактного тестирования на основе кодов, локализующих ошибки.

Практическая ценность. Концепция модифицированной блочной конструкции проверочных матриц двоичных линейных покрывающих кодов, на основе которой построены бесконечные семейства кодов с малыми радиусами покрытия Я = 2,э и 4, применима для получения кодов с радиусами покрытия Д > 5.

■ С помощью разработанного алгоритма декодирования и построенных проверочных матриц двоичных кодов БЧХ с минимальным расстоянием б может быть осуществлена защита от ошибок, возникающих при хранении информации в полупроводниковых запоминающих устройствах суперЭВМ и учитывающая их байтовый характер.

Предложенный метод контроля и диагностики конструктивных блоков суперЭВМ на основе каскадного компактного тестирования с

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

Апробация работы. Основные результаты работы докладывались на семинаре отдела базового программного обеспечения Института проблем кибернетики РАН (1986 - 1992гг.), Всесоюзном семинаре молодых ученых и специалистов "Информатика и вычислительная техника" (г.Звенигород, 1986г.), III Международном семинаре по теории информации "Сверточные коды; связь со многими пользователями" (г.Сочи, 1987г.), I Всесоюзной конференции "Проблемы создания суперЭВМ, суперсистем и эффективность их применения" (г.Минск, 1988г.), IX Всесоюзной конференции по теории кодирования и передачи информации (г.Одесса, 1988г.), Научной школе-семинаре "Проблемы кибернетики" (г.Киев, 1990г.), и Международной конференции АССТ-2 (г.Ленинград, 1990г.), III Международной конференции АССТ-3 (Болгария, 1992г.).

Публикации. Представляемые к защите результаты опубликованы в работах [1 — 11].

Объем и структура диссертации. Диссертация состоит из введения, трех глав, заключения, приложения. Ее общий объем 109 стра- • ниц, в том числе 6 рисунков, 3 таблицы и список литературы из 57 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

странстве f^ n-мерных векторов над полем GF(2) найти множество кодовых слов, задающих код с длиной п и избыточностью г, таких, что шары радиуса Я в метрике Хэмминга с центрами в этих кодовых словах покрывают все точки пространства. Эти кода называются покрывающими 1п,п - г]Я кодами, с радиусом покрытия R.

Для сравнения покрытий пространства порождаемых двоичными линейными покрывающими кодами, используется функция Олины 1(г,Я), которая задает наименьшую длину покрывающего кода с избыточностью г и радиусом покрытия R. Нижняя граница 1(г,Д) определяется из мощностншс соображений. Верхнюю границу, получают конструктивно. явным образом задавая покрывающий код или определяя способ получения таких кодов с помощью алгоритма построения соответствующих проверочных матриц. Качество построенных покрытий характеризуется плотностью покрытия, которая для кода Un определяется следующим образом:

Я Я

Ц(П,Я,{/П) й 2П_Г(ип) Е с'/2П= Е C*/'2r(ffn).

1=0 1=0

Для характеристики бесконечного семейства кодов U с радиусом покрытия Я, где Un- код длины п из этого семейства применяется асимптотическая плотность-.

¡¡{R.U) й lim inf \i(n,R,U„), n — о Un<c U n

(Далее вместо обозначения ц(Я,1?) используется ц(Я), т.к. семейство U определено из контекста.)

В §1.1 предложена модификация блочной конструкции проверочных матриц двоичных линейных покрывавдих кодов, которая на основе начального покрывающего кода с радиусом покрытия Я порождает бесконечнее семейства кодов с тем же радиусом покрытия.

Для описания' свойств покрывающего кода использовано понятие [п,п - r]R,l кода, а для описания множества столбцов его проверочной матрицы введено понятие (Я,Х Достаточного разбиения на подмножества. На основе исследования структуры множества столбцов проверочной матрицы начального кода, использупцего (Я,!)-достаточные разбиения на подмножества, расширена область применения

блочной конструкции. Обобщенная конструкция названа "Конструкцией А".

В этой конструкции использованы матрицы Р^ср) и где

О 6 СР(2т) и {*>. имепцие вид:

Р®(Ф) й Сф ... ф]. ф е вГ(ге).

Число столбцов в матрице Р^ф) определяется в зависимости от конкретных условий.

В**<&) 6

е0Ъ е^Ъ

вШ

ецЬ

е^'1 е^'1 ... е„Ья"1

для Ъ£СР(гт),

В^С») й

ео е1

где верхний индекс Ь есть показатель степени, * = 2я - 1, Ь, вJ, е гм), / = о7*. и = 1 ,Й-1; к еслн е.* вле-

мент Ь называется индиааторол матрицы

Конструкция А.

Пусть начальный коО 70 является двоичным линейным «3,0 - а]Я,10 кодом с проверочной матрицей

Ф8 = [<р, ... фд1, ф4 еСР(28), I - ТТЗ-

Пусть К - (Я,10)-достаточное разбиение множества столбцов матрицы Ф8 на Л(Ф®, 10;Я) подмножеств. Определим новый двоичный линейный коО 7 с помощью проверочной матрицы

о8

jjnR

uS+тЯ

на

где т > 1 целое, а - индекс матриц Z^ и - Оополняющая

поОлатрица к множеству матриц UP*«»,).....^(bn )}. Индикаторы

Ь( выбираются следующим образом: если столбцы <р1 и (pj из ®s принадлежат различным подмножествам К тогда всегда bj *

Выбор индикаторов осуществляется в соответствии со случаями Л1 или А2:

Q

Случай А1. U bt С С?(2т) и {»} \ Т, 2т + 1 - |Г| > /г(Ф8, lQiK). 1 = 1

где |Т| - мощность множества Г и возможны следующие варианты: Т ~ 0, Г с GP{2m) и {*}; |Г| > 1, т.е. Т = {«}, Г = {»,0}, Г = {»,1),

Т = {а-': 3 = üTc}, а - примитивный элемент поля GF(2m), с < 2й-2. Вид подматрицы Г^ зависит от параметра lQ начального кода VQ. Q

Случай А2. U &[= С?(2т)и{*}УГ, Q > 2т + 1 - |Г| > П(ФВ,10;К), t = 1

где возможны следующие варианты: Т = 0; Г = {»}. Здесь необходимо использовать все элементы поля GF(2n) в качестве индикаторов Ь. Вид дополняющей подматрицы не зависит от параметра начального кода VQ.

При этих условиях новый код V является нормальным [п.п - r]R,l кодом с I > lQ, радиусом покрытия Я, избыточностью г = s + wR и длиной п = 2mQ + N„(m), где /Mm) - число столбцов в

е ■ ■

Случай А1 конструкции А доказан ранее А.А.Давыдовым. Случай А2, оценки параметров I и для построенных кодов V

и некоторые варианты случая А1 являются новыми результатами.

Процесс построения проверочных матриц с помощью конструкции А является итеративным. Можно применять проверочную матрицу

кода V, полученную на t-ом шаге, как проверочную матрицу фе+тй начального кода VQ для (t + 1)-ого шага. Более того, для одного и того же начального кода' VQ возможно использование обоих случаев

А1 И А2.

В §1.2 доказана теорема 1.1, определяющая алгоритм not троения двоичных линейных покрывающих кодов с радиусом покрытия Я = 2 на основе конструкции А. Указан вид подматриц и даны оценки параметров I и Mi/®"™*2) для построенных кодов. По теореме 1.1 получены бесконечные семейства покрывающих [п,п - r]2,I кодов с параметрами:

Г = 2 t, i > 4, П = 27x2t~4 - 1, г = О, Ц(2) % 1 .423Э; '

Г = 2t - 1, t > Э, п = 5x2t-2 - 1, г = О, [1(2) % 1 .5625.

В §1.3 аналогично теореме 1.1 доказана теорема 1.2 о модификации конструкции проверочных матриц А для кодов с радиусом покрытия Я = з. С помощью этой теоремы построены бесконечные семейства покрывающих ln,n - г]3,1 кодов с параметрами:

Г = 3t - 1. t > 14, П = 821х2*~9 - 1, l > 1, ¡¡(3) % 1.3744s

Г = 3t - 2, t > 8, П = 3x2t_1 - 1, 1=2, ¡1(3) % 2.25S

Г = 3t, t > 6, n = 155x2i_6 - 2, I > 1, ¡1(3) % 2.3676.

В §1.4 в теореме 1.3 конструкция А рассмотрена для случая Я = 4 и получены следующие семейства [п,п - г]4,1 кодов:

Г = 4t ~ 2, t > 16, n = 991x2t-9 - 1, 1 > 2, ¡1(4) » 2.3391;

г = 4t, t = 5, t > 11, n = 47x2i_4 -1,1=3, ¡¡(4) * 3.1024;

Г = 4t - 1, t « 9, t > 16, П = 1247x2t_9 - 1, Z = 3,

Ц(4) й 2.9323;

Г = 4t - 3, t > 16, П = 895x2t_9-1, Z = 3, ¡¡(4) » 3.1124.

Асимптотические плотности покрытия построенных семейств двоичных линейных кодов с Я = 2,3 и 4 являются в настоящее время наилучшими среди известных кодов.

Полученные кода уменьшают ранее известную конструктивную верхнюю границу функции длины 1(г,Я).

В 51.5 все улучшения для верхней границы l(r,R) при г < 64, R = 2,3 и 4 сведены в табл.1.

Идеи и подхода, использованные в этой главе для кодов с радиусами покрытия Я < 4, можно применить (с некоторыми модификациями) для построения кодов с радиусами покрытия Я > 5.

Вторая глава посвящена разработке алгоритма декодирования, построению проверочных матриц двоичных кодов БЧХ с минимальным расстоянием 6, исправляющих помимо двойных независимых ошибок одиночные байты ошибок длины 4 и оценке их обнаруживающей способности.

В §2.1 рассматриваются свойства проверочных матриц и алгоритм декодирования таких кодов.

, Проверочная матрица Н расширенного двоичного [п,п - г]-кода БЧХ с расстоянием <2=6, длиной п < 2т, числом информационных символов п-г = /1-2т-1,т>4 записана в виде:

Л • • • V "

н = ... < = нз

1 1 ... 1 . J

где Л - локатор /-Й позиции кодового слова; Н^- матрица локаторов; Нэ - матрица кубов локаторов; J - строка из единиц.

hJ * hJ при * .= ТТп. (1)

Локаторы и кубы локаторов при декодировании и описании свойств матрицы рассматриваются как элементы поля вПгт).

Обозначим; а' = (о,', а^,;.., а^) - декодируемое слово; а^ б {0,1}, } = 1,п; "штрих" указывает, что символы декодируемого слова могут оказаться искаженными; ц = |п/4|; ^ - целая часть х. Тогда любое искажение декодируемого слова в пределах позиций с номерами - Э, 41 - 2, 41-1, 41 (где I = ТТц) называется 1-д байто- ошибок длины 4. Если искажены все четыре символа а4(-2' а4(_1» а4( > то имеет место байт ошибок влит 4 веса 4 {сплошной байт ошибок). Если искажены любые три из этих символов (например, , а четвертый символ ) не ис-

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

Сумму кубов локаторов, соответствующих 1-му байту ошибок, назовем указателе* 1-го'баОш ошибок и обозначим

ft = ^i-э + + h^t-1 + Л41 > t = ТТЦ. и = Ln/4j

? - i/.). /2* '••* ty ~ совокупность всех указателей.

Пусть локаторы в матрице Н1 расставлены так, что выполняются соотношения

h4t-3 + h4i-2 + Л41-1 + h4l = 0 ' 1 = ^ (2)

ft* fj при £ ^ /5 £ = ТТГГ. (3)

Эти условия позволяют при декодировании отличать байты ошибок длины 4 веса 4 друг от друга и от двойных независимых ошибок. (Существование таких расстановок локаторов показано в §2.3).

Алгоритл декодирования В.

• Для декодируемого слова а' вычисляется синдром 5 = (51= a'Htr, где S1 = a'H1tr, a'H3tr, P = a'Jir' - общая проверка на четность. Решение принимается следующим образом.

1. Если Р = о, S1 = Sj = о , то ошибок неч'.

2. Если Р = 1, S3 = S1; S £ {fy,..., то произошла одна ошибка на позиции с локатором S1.

3. Если Р = О, S1 * 0; yv уг 6 .....где у;,, у2 - корни многочлена у2 + S^y + (S3/51 + S^), то произошли две независимые ошибки на позициях с локаторами у1, у2.

4. Если Р = О, S1 = О, S3 б F. то имеет место байт ошибок длины 4 веса 4 с указателем S

5. Если Р = 1, Sj * S1, S^ + S^ = /t e F и локатор входит в байт с указателем (т.е. S1 = J = 075). то имеет место байт ошибок длины 4 веса 3 с указателем Позиция с локатором 51 не искажена, остальные три позиции байта искажены.

6. Если не имеют места ситуации 1-5. обнаружена неисправимая ошибка.

В алгоритме шаги 1-3 стандартные. Для шагов 4,5 существенно, что все байты ошиббк имеют разные указатели . При выполнении шага 5*подразумевается, что байт ошибок длины 4 веса 3 более вероятен, чем три независимые ошибки. При выполнении шага 6 обнаруживаются (т.е. классифицируются как неисправимые) те конфигурации тройных

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

В $2.2 исследована структура множества столбцов проверочных матриц рассматриваемых кодов БЧХ.

Для этого введено понятие слоя - множества наборов вида (а, Ь, с, d), где a,b,c,d элементы поля GF(2m), одновременно удовлетворяющие условиям: а+Ь+с + с!=ои а3 + Ьэ + с3 + d3 = / * о. Эти наборы трактуются как четырехкратные ошибки в кодовом слове, определяемые столбцами проверочной матрицы И.

Доказаны лек-лы 2.1 - 2.2 и теорема 2.2 о структуре и мощности слоя Vj. На их основе доказана теорема 2.3 о количестве совпадений произвольного синдрома байта ошибок длины 4 с синдромами независимых ошибок.

Теорема 2.3: () Количество совпадений синдрома байта ошибок длины 4 веса 4, лежащего в слое Nj, с синдромами четырехкратных независимых ошибок равно:

если m - нечетное, (22хШ~3 - гт-2)/з - 1;

если т - четное,

(22хт-з _ (_2)Зхяг/2-2 _ гт-2)/3 _ 1 прИ р _ 0 (mod 3)>

(22xm-3 _ (_2)3xm/2-3 _ 2т"2)/з - 1 при р * О (mod 3),

где / = аР, а - примитивный элемент поля GF(2m).

II) Количество совпадений синдрома байта ошибок длины 4 веса 3, лежащего в слое Nj,, с синдромами трехкратных независимых ошибок равнр:

если п - нечетное, (2й-1 - 1)/з - 1; ее ! т - четное,

(2П~1 -' (-2)m/2 - 1)/3 - 1 при р S О (mod 3), (2m_1 - (-2)m/2~1 - 1)/3 - 1 при p jt 0 (mod 3),

где f = a?, a - примитивный элемент поля GF(2m).

В табл.2 для полей GF(2m), где т = 4,5,6,7. приведены базовые наборы, определя.ющие для заданного / слой Hf.

В §2.3 предложена конструкция проверочных матриц кодов БЧХ, исправляющих байты ошибок.

Теорема 2.4: Пусть Г = ... tp] матрица размера (т - 1)хр, где р = л/2, каждый столбец является (т - 1)-мерным представлением элемента поля СР(2т~1) и

при й * I; к,1 = Т7р;

при I * 3} 1,3 = 1,р/2

Определим матрицу Н1 размера т*п, где п = 2р:

+ *2( " *2./-1 +

Я,

«1 «2 *2

0 10 1

«3 'э *4 *4

0 10 1

V1 V *Р

При построении ^ каждый столбец записывается дважды. К первой записи снизу приписывается ноль, ко второй - единица. Тогда столбцы матрицы Н^ удовлетворяют условиям (1)-(Э).

В §2.4 построены примеры проверочных матриц рассматриваемых кодов БЧХ, в полях 2т), где т - 4,5,6,7,8.

В §2.5 дана оценка обнаруживающей способности алгоритма декодирования кода БЧХ (алгоритм В), который может обнаруживать (т.е. классифицировать как неисправимые) конфигурации тройных независимых ошибок, синдромы которых не совпадают с синдромами байтов ошибок длины 4 веса з и конфигурации четырехкратных независимых ошибок, синдромы которых не совпадают с синдромами двойных независимых ошибок и с синдромами сплошных байтов ошибок. В этих случаях происходит отказ от декодирования.

Способность алгоритма обнаруживать независимые ошибки характеризуется величиной Д{ = где - число обнаруживаемых конфигураций 1-кратных независимых ошибок, У( - общее число (-кратных независимых ошибок. доля обнаруживаемых конфигураций (-кратных независимых ошибок от общего числа таких ошибок).

Пусть Ь£ - число конфигураций байтов ошибок длины 4 веса- ( в коде длины п; - число необнаруживвемых конфигураций 1-крадтшх независимых ошибок.

Теорела 2.5: При декодировании кода БЧХ длины п < 2Щ, исправляющего двойные независимые ошибки и байты ошибок длины-4 веса 4

и 3. доля обнаруживаемых тройных и четырехкратных независимых ошибок составляет . • . ,

А3 = 1 - 83/(Сд - п), где g3 < i/3(b3(2m_1 - 4) + 7(-2)m/2"1 (12К - ri));

¿4 = 1 -g/(4~n/4),

где

g4 < 1/3b4(22n~3 - 2m~2 - 3) + 7/3(-2)3m/2~5(12K - П) + 15i46(n)ï

К - число кубов в F (т.е. К - число указателей байтов ошибок, являющихся кубом некоторого элемента поля GP(2m)); 7 6 (0,1), 7 = m + 1 (mod 2). 4g(n) - число слов веса 6 в рассматриваемом коде БЧХ длины п.

В табл.3 для построенных в §2.4 матриц приведены числовые характеристики, описывающие совпадение синдромов байтов ошибок длины 4 и независимых ошибок. Например, для [79,641-кода обнаруживается более 99,5% тройных и более 8055 четырехкратных независимых ошибок.

§2.6 посвящен описанию блок-схемы реализации на БИС параллельного декодера кода БЧХ, исправляющего двойные независимые ошибки и одиночные байты ошибок длины 4.

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

В настоящее время в суперЭВМ выбор объектов тестирования осуществлен по функциональному признаку с учетом их электрических связей. Соответственно этому разбиению при тестировании используются функциональные тесты, позволяющие проверить правильность работы логических элементов и электрических функциональных связей в устройствах. Однако целесообразно и другое разбиение - на конструктивные элементы, которое выполняется из соображений минимизации критических связей между элементами и, как правило, не совпадает с функциональным разбиением. Тесты, основанные на этом разбиении, позволяют при контроле, особенно в процессе наладки, максимально проверить отдельные конструкции, имея непосредственный доступ к триггерам.

В §3.1 предложен метод компактного тестирования конструктив-

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

- состоит из объектов тестирования (блоков), отказы которых возникают независимо;

- вероятность одновременного отказа нескольких блоков пренебрежимо мала;

- каждый отказ проявляется в неправильных (неэталонных) состояниях некоторых выходов блоков, совокупность которых называется об-раэол отказа.

Каждый такт синхронизации на входы каждого тестируемого блока ( (( = 1,т) подается фрагмент тестовой последовательности, а с выходов блока снимается поразрядное двоичное слово (выходные, сигналы элементов этого блока). Выходные двоичные последовательности Г{ длины л£ блоков £ = 1 ,т записываются в т*к двоичную матрицу Ы так, что 1-ая строка содержит выходы 1-го блока (I = 1,т), а число столбцов к равно максимальному числу выходов среди всех т блоков к = шах (свободные позиции в строках матрицы Ы

заполняются нулями).

Каждая строка матрицы Ы рассматривается как информационные символы кодовых слов двоичного [й + г,Л]-кода 7, где г - число проверочных символов этого кода. С помощью проверочной матрицы кода 7 (называемого внутренним) для каждой информационной последовательности Г( вычисляется последовательность проверочных символов 1£ длины г и формируется двоичная матрица проверок Р так, что (-ая строка Р (последовательность 1{) содержите проверочных символов для 1-ой строки к (последовательности Г{).

Для матрицы Р вводится ч-ичное представление Р^ (д. = 2*) и столбцы матрицы Рд рассматриваются как информационные символы-[т + ц,т]-кода (Т (называемого внешним) над полем СР(2*), где 2* > т + ц, р. - число проверочных символов кода (Т. Формируется <3^ -матрица проверочных символов кода V так, чтобы т информационным символам, находящимся в У-ом столбце матрицы Рд, соответствовали ц проверочных д-ичных символов (двоичных последовательностей С,), находящихся в J-or^ столбце матрицы а .

Сигнатурой отказа (синдромом кода, локализующего ошибки) называется д-ичная матрица = <3^ - С®, где С® - матрица эталонных д-ичных проверок для данного такта тестирования.

Избыточность (объем эталона) рассмотренной каскадной конструкции составляет Як = цг двоичных символов (Як = 24г или Яд = (2í+ 1)г символов при локализации I отказавших блоков или обнаружении < + 1 отказавшего блока).

Применение описанного метода дает выигрыш в п/ф раз в объеме памяти, затрачиваемой на хранение эталонов, по сравнению с традиционными методами тестирования.

В §3.2 рассмотрен пример выбора внутреннего V и внешнего И кодов для контроля и диагностики суперЭВМ.

В качестве кодов V и (Г выбраны, соответственно, двоичный циклический код с порождающим многочленом 8(х) степени г (реализованный алпаратно на сигнатурном анализаторе) и код Рида-Соломона с минимальным расстоянием а = 4 над полем С?(2Г). Часто г выбирают 16. В этом случае при отказе одного блока он обязательно будет локализован, а при отказе двух блоков система диагностику сообщит о невозможности локализации отказа, но не выдаст неверного сообщения.

Код РС с а = 4 над полем С7(2Г) реализован прог^ммно на управляющей ЭВМ, специально предназначенной для управления и тестирования суперЭВМ, в памяти которой хранятся эталонные локализующие сигнатуры Сэ(Г) для каждого выбранного такта синхронизации т. Они состоят из трех г-разрядных слов С®, о|, сЦ, сформированных следующим образом: т

С* = Е I? аи-1)(т-1), ; = 1,2,3, 1 = 1

где -эталонная сигнатура 1-го этапа для 1-го блока, рассматриваемая как элемент поля СР(2Г). Значения не хранятся в памяти УМ, а нужны только при вычислении эталонных локализующих сигнатур, которые являются проверочными символами кода РС с й = 4.

п1 разрядов

п^ разрядов

сигналы выходов

Г =

КГ) =

сигнатура I этапа

С(Т) = локализующая сигнатура

£1

I этап

У

г разрядов

г разрядов

ч

г разрядов

сравнение 0.,+ С*

Сэ = эталонная локализующая сигнатура

С2

сравнение э2= с2+ с|

гэ 2

С3

сравнение Б3= С3+ С\

С* _

II этап

хранится в памяти УМ

Рис.1. Схема компактного тестирования суперЭВМ.

Сложность этого алгоритма % зт и определяется количеством выполняемых операций умножения. Объем памяти, необходимый для хранения эталонной локализующей сигнатуры С9(Г), полученной для одного такта синхронизации, составляет 3г разрядов.

§3.2 посвящен вопросам расширения диагностических возможностей метода компактного тестирования. Приведена блок-схема алгоритма локализации двух отказавших блоков. Расширение корректирующих возможностей метода компактного тестирования (способность локализовать два неисправных блока) влечет за собой увеличение сложности алгоритма по сравнению со сложностью алгоритма локализации одного неисправного блока в 7/6т раз. При этом объем памяти суперЭВМ, необходимый для хранения эталонных структур, остается прежним. г

В приложении приведена программа, реализующая алгоритм определения исправности конструктивных блоков суперЭВМ с использованием кода Рида-Соломона с расстоянием 4. Программа написана на

С

языке СИ.

основные РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Построены бесконечные семейства покрывающих кодов с малыми радиусами покрытия Я = 2,3 и 4. Асимптотические плотности покрытия этих семейств являются в настоящее время наилучшими среди известных кодов.

3. Уменьшена верхняя граница функции длины I(г,Я), задающей наименьшую длину покрывающих кодов при фиксированных г и Я. Все улучшения для Цг,Я) при г < 64, Я = 2,3 и 4 сведены в таблицу.

4. Разработан алгоритм декодирования двоичных кодов БЧХ с минимальным расстоянием 6, способный исправлять двойные независимые ошибки,одиночные байты ошибок длины 4 веса 4 и 3 и обнаруживать часть четырехкратных ошибок.

5. Исследована структура и предложен итеративный способ построения проверочных матриц кодов БЧХ, исправляющих байА ошибок.

6. Получены оценки обнаруживающей способности алгоритма декодирования кодов БЧХ, исправляющих байты ошибок.

7. Описана блок-схема реализации на БИС параллельного декодера кодов БЧХ, исправляющих двойные независимые ошибки и одиночные байты ошибок длины 4.

8. Разработан каскадный метод компактного тестирования на основе кодов, локализующих ошибки, для контроля и диагностики суперЭВМ.

9. Предложена аппаратно-программная реализация метода компактного тестирования, подробно описаны алгоритмы локализации одного и двух отказавших блоков, использующие коды Рида-Соломона о расстоянием 4.

По теме диссертации опубликованы следующие работы:

1. Афанасьев В.Б., Грибачев С.А., Давыдов A.A., /¡рохжина-Лавин-ская A.D., Шнитлан В.З. Использование кодов, локализующих ошибки, для диагностики супер-ЭВМ.- IX Всесоюзн. конф. по теории кодирования и передачи информации, тез. докл., ч.1, Одесса, 1988, с.164-166.

2. Афанасьев В.Б., Грибачев С.А., Давыдов A.A., ¿рожхина-Лабин-ская A.D., Шнитлан В.З. Контроль и диагностика суперЭВМ методом компактного тестирования на основе кодов, локализующих ошибки.- Вопросы кибернетики. Прикладное программное обеспечение и моделирование суперсистем. ВК-155, М., Научн. совет по комплексной проблеме "Кибернетика" АН СССР, 1991, с.152-163.

3. ¿рвъдов A.A., Ароххина-ЛпОинская A.D. Исправление байтов ошибок длины 4 и двойных независимых ошибок кодом Боуза-Чоудхури-Хоквингема в полупроводниковых запоминавдих устройствах.- Автоматика и Телемеханика, М., 1989, с л35-146.

4. /рвыдов A.A., Ароххина-АаОинская A.D. Исправление байтов ошибок длины 4 и двойных независимых ошибок кодом БЧХ в полупроводниковых ЗУ супер-ЭВМ.- I Всесоюз. конф. "Проблемы создания супер-ЭВМ, супер-систем и эффективность их применения", тез. ДОКЛ., 4.2, МИНСК, 1987, С.137-139.

5. /¡рвыдов A.A., /рохжина-Аабинская A.D. Построение верхней границы длины двоичных линейных кодов с радиусом покрытия Д = 3. - Методы и программные средства оптимизации, моделирования и создания вычислительных систем, сб. научн. тр., Ин-т кибернетики АН УССР, Киев, 1990, с.34-36.

6. ¿рвыдов A.A., /рохжина-Аабшская A.D., Ксиинчева В.В. Реализация на БИС параллельного декодера кодов БЧХ, исправляющих двойные независимые ошибки и байты ошибок длины 4.- Вопросы кибернетики. Базовое программное обеспечение суперЭВМ. ВК-145, М., Научн. совет по комплексной проблеме "Кибернетика" АН СССР, 1990, с.151-174.

7. /рвыдов A.A., Ароххина-Лабинская A.D., ТолОан Л.М. Дополнительные корректирующие возможности кодов БЧХ, исправляющих двойные и обнаруживающих тройные ошибки. - Вопросы кибернетики. Комплексное проектирование элементно-конструкторской базы

ЭВМ. ВК-142, М., Научн. совет по комплексной проблеме "Кибернетика" АН СССР, 1988. с.86-113.

8. Давыдов А.А., Арожжина-Лабинская А.С., ТолОак A.M. Коррекция байтов ошибок длины 4 и двойных независимых ошибок кодом БЧХ с расстоянием 6. - III Меадунар. семинар по теории информации "Сверточные коды; связь со многими пользователями", тез. докл., Сочи, 1987, с.48-51.

9. Арожжина-Аабинская A.D. Исправление байтов ошибок в полупроводниковой памяти ЭВМ большого объема кодами БЧХ. - Всесоюзн. семинар мол. ученых и специалистов по информатике и выч. технике, тез. докл., М., 1986, с.96-97.

10.Davydov А.А., DrozhzhIna-LabСnstoya A.Yu. Binary linear codes with covering radii 3 and 4. - XI Internation. workshop "Algebraic and combinatorial coding theory", abetr., Leningrad, 1990, p.56-57.

11.Davydov A.A., Drozhzhlna-Iablnskaya. A.Yu. Constructions of binary linear covering codes. - III Internation. workshop "Algebraic and combinatorial coding theory", abetr., Bulgaria, 1992, p.51-54.