автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Методы помехоустойчивого кодирования и их применение в полупроводниковой памяти высокопроизводительных ЭВМ

КОМИТЕТ ПРИ ПРЕЗИДЕНТЕ РФ ПО ПОЛИТИКЕ ИНФОРМАТИЗАЦИИ РОССИЙСКАЯ АКАДЕМИЯ НАУК

Всероссийский научно-исследовательский институт проблем вычислительной техники и информатизации

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

Специальность 05.13.13 - Вычислительные машины, комплексы,

системы и сети

Р Г Б ОД

' О ОКТ

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

Бояринов Игорь Маркович

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Москва - 1994

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

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

доктор технических наук, член-корреспондент ИА РФ В.В.ЗЯБЛОВ доктор технических наук В.З.Шнитман доктор технических наук, профессор А.Л.Щбрс

заседании специализированного совета дльз.ш .<л при Всероссийском научно-исследовательском институте проблем вычислительной техники и информатизации по адресу : 113114, Москва, 2-ой Кожевнический пер., дом 4/6.

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

Ведущая организация:

Московский физико-технический институт

Защита состоится

часов на

Автореферат разослан

Ученый секретарь специализированного совета доктор технических наук

Р.Г.ВИЯШЕВ

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

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

Плотность БИС, объем полупроводниковой памяти, быстродействие вновь создаваемых ЭВМ непрерывно растут, что вызывает необходимость для обеспечения требуемой надежности применения таких схем кодирования, которые позволяют исправлять кратные ошибки как в машинном слове, так и в БИС памяти.

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

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

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

Цель работы. Разработка и исследован?"1 методов построения и алгоритмов декодирования кодов, предназначенных для обнаружения и исправления ошибок в полупроводниковой памяти высокопроизводительных ЭВМ. Построение и исследование быстрых параллельных конвейерных схем декодирования таких кодов. Построение и исследование свойств самопроверяюшихся алгоритмов и схем декодирования.

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

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

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

Исследованы свойства и построены алгоритмы декодирования прямых сумм произведений кодов.

г

Исследованы свойства и разработаны конструкции линейных кодов с неравной защитой информационных стволов.

Разработаны и исследована алгоритмы и схемы параллельного декодирования на БИС и СБИС кодов с минимальной или близкой к минимальной избыточностью, исправляющих двойные и тройные независимые ошйбки и одиночные Сайта ошибок.

Построены элементы теории самопроверящихся алгоритмов декодирования линейных кодов. Разработаны и исследованы самопроверяющиеся алгоритмы декодирования кодов БЧХ, исправляющих многократные ошибки.

Построены полностью самоггроверяющиеся схемы кодирования и декодирования кодов Хэммннга с минимальным расстоянием а = 3, модифицированных кодов Хэмминга с <1=4, кодов БЧХ с а = 6.

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

Реализация исследований. Результаты работы были использованы при проектировании основной и внешней полупроводниковой памяти суперЭВМ " Электроника СС БИС

Апробация работы. Основные результаты диссертации докладывались : на VII Всесоюзном симпозиуме по проблеме избыточности в информационных системах (Ленинград,1977 г.), на VII .Всесоюзной конференции по теории кодирования и передачи информации (Вильнюс,1978 г.), Пятом международном симпозиуме по теории информации (Тбилиси,1979 г.), на I Всесоюзной конференции " Проблемы создания суперЭВМ, суперсистем и эффективность их применения (Минск,1987 г.), на II Международном семинаре по алгебраической и комбинаторной теории кодирования (Ленинград, 1990 г.), на Пятом объединенном советско-шведском международном семинаре по теории " информации (Москва,1991 г.), на семинаре отдела базового программного обеспечения Института проблем кибернетики РАН и семинаре по теории кодирования Института проблем передачи информации РАН.

Публикации. По теме диссертации опубликовано 24 работы, в том числе монография, и получено 2 авторских свидетельства на

изобретения.

Объем работы. Диссертация состоит из введения, семи глав, заключения и приложения, изложенных на Зоб страницах. Она содержит 9 таблиц и 17 рисунков. Библиография включает 167 работ.

СОСТОЯНИЕ ВОПРОСА И ЗАДАЧИ ИССЛЕДОВАНИЯ

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

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

Имеется целый ряд обзорных статей, позволяющих получить информацию о состоянии вопроса и проследить тенденции развития. В этом ряду обзоры Стифлера и Прадхана (1980 г.), Берниковского, Конопелько и др. (1933 г.), Чена и Сяо (1984 г.)-,- Фудзивары и Прадхана (1990 г.), Ивэдари, Фудзивары и др. (1991 г.), Сагалови-ча (1991 г.).

Наконец, имеется ряд книг, целиком или частично посвященных проблемам исправления ошибок в полупроводниковой памяти. Отметим книги Сивиорека и Шварца (1982 г.)", Лина и Костелло (1983 г.), Конопелько и Лосева (1936 г.), Огнева и Сарычева (1986 г.), Горшкова (1987 г.), Щербакова (1989 г.), Pao и Фудзивары (1989 г.).

Корректирующим кодом, применявшимся в ранних системах памяти ЭВМ, был код Хэмминга, исправляющий одиночные и обнаруживающий двойные независимые ошибки. В настоящее время в полупроводниковой памяти применяется модифицированный код Хэмминга, предложенный Сяо (1970 г.). Проверочная матрица этого кода состоит из столбцов нечетного веса.

В связи с тенденцией увеличения плотности БИС и объемов памяти находят применение коды со все более мощными корректирующими свойствами.

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

Полупроводниковая память суперЭВМ в большинстве случаев

строится на БИС памяти с одноразрядной организацией к казвдый разряд кодового слова размещается в отдельной микросхеме. Любая неисправность одной из БИС памяти приводит не более чем к одной ошибке в кодовом слове. Одиночные отказы и сбои периферийного логического оборудования могут привести к одиночным байтам ошибок и к;доъом слове.

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

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

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

Б этой связи основными задачами представленной диссертации являются :

- разработка и исследование методов построения и алгоритмов декодирования кодов, предназначенных для обнаружения и исправления ошибок в полупроводниковой памяти высокопроизБодительныхЗВМ ;

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

- построение элементов теории самопроверяюшкхся алгоритмов декодирования линейных кодов ;

- разработка и исследование самопроверяющихся алгоритмов декодирования кодов БЧХ, исправляющих многократные ошибки ;

- построение полностью самопроверяющихся схем кодирования и декодирования кодов Хэмминга с минимальным расстояние <1 = 3, модифицированных кодов Хэмминга с & = 4, кодов БЧХ с й = 6.

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

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

с

J

Первая глава посвящена декодированию в обобщенной метрике и связанны!«! с ним методам комбинирования кодов.

В § 1.1 вводится обобщенная метрика и рассматриваются два метода (общий и мажоритарный) декодирования в этой метрике.

Обобщенная лещша. Пусть Z - линейный (n,k)~ код над GF(q) с минимальным расстоянием Хэмминга d, у = (у1Гу2,..., у ) - слово с символами из алфавита П , состоящего из элементов поля GF(q) и символа х , 'называемого стертым символом или, кратко, стиранием. Если в слове у нет стертых символов, то существует не более одного кодового слова z = (z1 ,z2,...,z ) кода z такого, что d(y,z) < <3/2, где d(y,z) - расстояние Хэмминга между у и z . Если в слове у имеется m стертых символов, то в коде z существует не более одного слова z' такого, что s + m/2 < л/2, где s - число нестертых позиций, в которых у и z' различаются.

Теперь предположим, что о каждом символе у^ слова у = (у.ру2,---,уп) имеется дополнительная информация, выражаемая числом 0 < < 1/2, называемым коэффициентом недосто-

верности символа , i = 0,1,...,n . Стертым символам, если таковые имеются в слове у , присваивается наибольший коэффициент недостоверности, равный 1/2. Будем считать, что все символы любого слова кода z имеют коэффициент недостоверности, равный нулю. Таким образом, каждому слову у = (у,,у~,...,у„) с симво-

^ п (v\

лами из алфавита П ставится в соответствие вектор ßv,y' = <p1(y),ßjy>.....0 < ß}y> < 1/2, i = 1,2.....a. _

Пусть даны два слова у = (у1 ,у2,... ,уп) и z = (z~z2, :.. ,гд) с векторами недостоверности = и ß^ =

... ) соответственно. Пусть |а| - модуль а и

n f |ߣy) - ß|a)|, если у± = zv

d0(y,z) = • J , ф1 = 1

i=i [ 1 - Ißi5^ - если y^ si.

Показывается, что функция dQ(y,z) является метрикой. Она называется обобщенным расстоянием между у и z. Если у и z - кодовые слова, то dQ(y,z) совпадает с расстоянием Хэмминга d(y,z) между у и z .

Общий летод декодирования в обобщенной метрике. Для определения по слову у = (у.,, у2,..., у ) и его вектору недостоверности = (ßfy\ß^.....кодового слова z = (г1,а2,...,

z ) кода Z используется следующий алгоритм.

Предположим, что для кода z имеется алгоритм исправления

ошибок и стираний, реализующий минимальное расстояние Хэмминга кода d .

Упорядочим символы вектора ß^ в виде убывающей последовательности, добавив к ним такое, что ßiy' > , :

piy) > ß(y) > ... > ß<y> > ... > ß<y> > .

11 x2 lm n xn+1

Будем последовательно для каждого m (и = 1,2,...,п+1) присваивать коэффициент недостоверности, равный 1/2, символам слова у, коэффициенты недостоверности которых расположены левее коэффициента с нижним индексом i (иными словами, считать эти символы стертыми), а остальным символам присваивать коэффициент недостоверности 0. Будем пытаться декодировать построенные таким образом слова у(т) с помощью алгоритма исправления ошибок и стираний.

Показывается, что если существует слово z е z такое, что dg(у,г) < d/2 , то хотя бы на одном шаге

dQ(y(m),z) = sm + m/2 < d/2 ,

где sn - число нестертых позиций, в которых и z разли-

чаются. С помошью алгоритма исправления ошибок и стираний по слову у^ на этом шаге определяется кодовое слово z .

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

Лемма 1.1.1. Для любого слова 'у = (у1,у2,...,уп) над алфавитом 0 существует самое большее одно кодовое слово z кода z такое, что

<jQ(y,a) < d/2 .

.rdomö того, не нужно делать все п + 1 шагов декодирования. Достаточно min {(d + 1)/2,и} шагов, где и - число различных коэффициентов недостоверности символов слова у .

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

Показывается, что если код Z допускает мажоритарное декодирование, то его декодирование в обобщенной-'метрике может быть существенно упрощено по сравнению с общим случаем.

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

В § 1.3 рассматривается метод декодирования произведений кодов, использующий декодирование в обобщенной метрике. Этот метод удобен при декодировании прямых суш произведений кодов.При исправлении только независимых ошибок он сходен с алгоритмом Юс-тесена (1972 г.).

В § 1.4 вводятся прямые суммы итеративных и каскадных произведений линейных кодов и приводится оценка их кодового расстояния. Для прямых сумм итеративных кодов оценка была получена Мар-чуковым (1968 г.), для обобщенных каскадных кодов - Блохом и Зяб-ловым (1973 г.). В следующих главах дается общий алгоритм декодирования и примеры использования этой конструкции в полупроводниковой памяти.

Глава 2 посвящена линейным кодам с неравной защитой информационных символов. Линейные кода с неравной защитой информационных символов (КЗ-коды) были введены Ыасником и Вулфом (1967 г.). Границы для произвольных КЗ-кодов были построены Бассалкго, Зиновьевым, Зяблевым, Пинскером (1979 г.), для линейных колов - Кацманом (1980 г.) и ван Гилсом (1984 г.).

Методы построения и алгоритмы декодирования рассматривались Гором и Килгусом (1971 г.,1972 г.), Мандельбаумом (1972 т"), Ды- -нькиным и Тогонидзе (1976 г.), Даннингом и Робинсом (1978 г.), Зиновьевым и Зябловым (1979 г.), Кацманом (1980 г.), ван Гилсом (1984 г.), Лином В. и' Лином Ш. (1990 г."Опт а также в работах [1-Ю], часть результатов которых использована в данной .главе.

Определения и основные свойства линейных НЗ-кодов приводятся в--§ 2.1. Пусть v - линейный, возможно, несистематический (п.к)-код над GF(q) с минимальным расстоянием Хэмминга d. Пусть было передано кодовое слово ь и принято слово Ъ' = (Ь|,... в = ь* - ъ = (е1,...,еп) - слово-ошибка. Будем предполагать, что при декодирования кода V находится ближайшее к принятому в смысле расстояния Хэмминга кодовое слово. Если при этом число ошибок в принятом слове не превосходит t- (t = | (d - 1)/2|.), .то .переданное слово-всегда находится правильно.

Допустим теперь, что число ошибок в принятом слове равно £ и г > 1; . В этом случае мы не можем гарантировать, что' результатом декодирования будет истинное кодовое слово. Однако, код V может иметь такие свойства, что некоторые информационные символы могут быть определены правильно.

Будем говорить, что 1-й информационный символ (1-й символ информационного слова) кода V имеет степень защиты г^, если какие бы зг (1 < х^) ошибок не произошли в произвольном кодовом слове ь, этот символ определяется верно при декодировании слова ь' = Ь + е, у;(в) = г в ближайшее к нему кодовое слово.

Кодг информационные символы которого имеют-различные степени зашты, называется кодом с неравной защитой информационных символов (НЗ-кодом).

Доказываются леммы 2.1.1 - 2.1.7, характеризующие различные свойства линейных нз-кодов. Наиболее часто в дальнейшем используются леммы 2.1.4 и 2.1.6.

,1ел«а 2.1.4. Для того чтобы к" информационных символов линейного (п.к)-кода V имели степень зашиты е, необходимо и достаточно, чтобы код V разлагался в прямую сумму V = V' © V" такую, что размерность V" равна к" и все слова V £ V веса не более 23 принадлежат V' .

Лелла 2.1.6, 1-й символ кодового слова линейного кода V имеет степень зашиты если и только если 1-й столбец проверочной матрицы н кода линейно зависит от или + 1 (но не меньше ) столбцов матрицы н .(Достаточность условия леммы доказана Масником и Вулфом (1967 г.)

В § 2.2 рассматриваются различные конструкции и алгоритмы декодирования соединений линейных КЗ-кодов. Одни из них основаны на соединении проверочных матриц кодов с заданными свойствами, в других используется соединение порождающих матриц. Типичным примером является следующая конструкция.

Теореш 2.2.2. Пусть аа I - целые числа такие, что {2Ь - 1,

1) = 1 , 1; > 3 . Тогда линейный двоичный (п,к)-код с

проверочной матрицей н^. ,

1 о ... о 0 ... о

1 о ... о рэ . . . о

о ... о

О

где о£ - примитивный элемент 0Р(22ш) и (3 = оС2 +1, имеет длину л = а2т-1, число проверочных символов г < (г + 1 )т, минимальное расстояние а = 3 и эквивалентен линейному систематическому коду в котором не менее чем 2Ш -(Ъ - 1)т -1 информационных символов инеют степень зашиты "г.

В § 2.3 рассматриваются прямые суммы произведений линейных кодов с неравной зашитой информационных символов и алгоритмы их декодирования.

Пусть заданы две последовательности линейных кодов. Последовательность V,, Ут кодов над стЧч) такова, что длины всех кодов одинаковы и равны пу , число информационных символов кода а = 1,2,...,и) равно ^ , для каждого 1 сумма V., + 7г + ... + прямая и минимальное расстояние кода ^ = У1 в У2 в ... в^ равно/ Последовательность г2,..., гт кодов такова, что длины всех кодов одинаковы и равны п2 ; Ц = 1,2, ...,т) есть либо код с символами из вРЫ , либо код с символами из СР(ак1) ; в обоих случаях число информационных символов кода %1 равно а минимальное расстояние равно Предположим, что ¿¡Б., < а^ < ... < 2тигп. Определим * как произведение кодов и , понимая под этим тензорное произведение 7, ® г- , если - код над ст1^ , и каскадное произведение г1, если - код над о?(ч г) .

Теорема 2.3.3. Сумма « + * %г +...+ V • гт - прямая ; и = * г1 в ?2 » г2 в.. .© Ут * гт - линейный (п,к)-код

над длины п_п„ с числом информационных символов - к

т т

= ^ к^ и минимальным расстоянием с^ > л, ; = £ к1к1

1=1 1=3 информационных символов кода и имеют степень зашиты не менее

5.= ка.в. -1)/2| .

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

Будем предполагать, что для кода имеется алгоритм декодирования, позволяющий исправлять (21^ + 1 < или меньше ошибок, а для кода имеется алгоритм исправления независимых

ошибок и стишниЯ, реализующий минимальное расстояние кода.

Пусть и' - принятое слово, и'=и+Е, и£и,г -. слово-ошибка. Учитывая, что слово и единственным образом представило в виде и = и, + и^ + ... , где ^ е = ^ • ъ^, 1 = 1,..

. ,т, декодирование слова и' будем осуществлять в т шагов. На нервом шаге по слову и' определим кодовое г^ и информационное ащ слова кода ит . На втором шаге по слову = и' -

определим кодовое ит_1 и информационное аю_1 слова кода ит_1 . На 1-м шаге по слову

"ю-(1-1 > = и' " "га-(1-2) " "т-Ц-З) " ~ "т

определим кодовое и[п_.ц_1 ^ и информационное ат-(1-1) слова кода ии_ц_1 ^. Наконец, на т-м шаге по слову й' = и' - - ид - ...- определим кодовое и., и информационное а1 слова кода и., и тем самым кодовое и = о, + г^ + ид + - • •+ .и^ и информационное а = а1 + а£ + ад + ,..+ а слова кода, и .

На 1-ом (1 = 1,...,т) шаге, декодируя слова-столбцы слова "¿-(1-1) с помощью алгоритма декодирования кода находим для слова вектор недостоверности = ,

Г ез / ^-(1-1) • есди ез < ^-(1-1 )/2 ' Р - = 1

3 [ 1/2 , в противном случае ,

где е • - число ошибок, исправляемых в о-том слове-столбце.

По слову и его вектору недостоверности |3' с

помощью метода декодирования в обобщенной метрике, рассмотренного в § 1.1, находим слово яа_ц_-)) кода 2ш-ц-1) такое, что

йО(2т-(1-1)' а1п-(х-1) Э < Вт-(1-1)/2 '

Теорема 2.3.6. Пусть код и 'удовлетворяет условиям теоремы 2.3.3 и а'=и + Е,и£и,Е- слово-ошибка. Если вес я(Е) < , то т-шаговый алгоритм декодирования кода и определяет истинные значения информационных символов подкода * в . .. в?в».гш кода и . При гс(Е) < алгоритм по и' нахо-

дит истинное кодовое слово и .

Прямые суммы произведений кодов могут быть использованы для исправления ошибок в составных и сложных каналах. В § 2.3 приводятся обобщения теоремы 2.3.3 на случай исправления разного типа группирующихся- ошибок в таких каналах.

Общий метод декодирования линейных НЗ-кодов, являющихся прямыми суммами произведений кодов, применим к декодированию обобщенных каскадных кодов. Первый алгоритм декодирования линейных обобщенных каскадных кодов был разработан Блохом и Зябловым (1973 г.). Алгоритм декодирования нелинейных обобщенных каскадных кодов был разработан Зиновьевым и Зябловым (1978 г.). Рассматриваемый в

§2.3 алгоритм является развитием этих алгоритмов. Сходные алгоритмы декодирования обобщенных каскадных кодов были предложены Думером (1980 г.) для независимых ошибок и Зиновьевым (1981 г.) для группирующихся ошибок.

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

Алгоритмы кодирования и декодирования состоят из операций в конечных полях к поэтому представляет практический интерес задача реализации этих операций на БИС и СБИС . Для эффективной реализации на БИС схемы выполнения операций должны быть однородными, т.е. состоять из блоков небольшого числа типов. При реализации на СБИС к этому добавляется требование регулярности и минимальности длин связей в блоках и между блоками. Конвейерность и параллельность выполнения операций - небходимое свойство схем при использовании их в высокопроизводительных ЭВМ. Наиболее подходят, для этих целей систолические и полусистолические алгоритмы и схемы.

Задачам реализации вычислений вычислений в полях Галуа на БИС и СБИС посвяшен § 3.1. Здесь же рассматриваются систолические и полусистолические схемы выполнения арифметических операций в GF(2Ш) с максимальным или близким к максимальному быстродействием.

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

Синдромы принятых кодовых слов находятся во всех методах одинаково. Методы отличаются друг от друга способами определения местоположения ошибочных символов. В паевой группе методов (декодеры I и II) локаторы ошибочных символов находятся посредством решения квадратного уравнения. Во втором методе (декодер III) решение принимается для каждого символа кодового слова отдельно .

Яри реализации декодеров первой группы используются БИС ПЗУ. Декодер III реализуется на больших интегральных схемах (например,

матричных БИС) без использования БИС ПЗУ и имеет в 2-3 раза большее быстродействие по сравнению с декодерами первой группы (временная задержка, вносимая БИС ПЗУ, составляет примерно 40% времени декодирования).

В § 3.3 рассматриваются методы параллельного кодирования и декодирования на комбинационных схемах кодов Препараты с минимальным расстоянием 6. Код Препараты является нелинейным, систематическим, квазисовершенным кодом и имеет на один проверочный символ меньше, чем расширенный код БЧХ той же длины а (п = г®*1, т -нечетное). При длине машинного слова к = 32,64 и 128 символов избыточность укороченного кода Препараты равна соответственно 12, 15 и 16 символам.

Известно несколько различных описаний кодов Препараты. Здесь используется описание этих кодов, принадлежащее Бейкеру, ван Лж-ту и Вильсону (1983 г.).

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

■ В первом методе вычисляются локаторы только ненулевых символов слова-ошибки. При этом параллельно выполняются такие разнородные вычисления, как решение двух квадратных уравнений, извлечение кубического корня из суммы кубов элементов СР(2т). Тем не менее при малых ю (т = 3 и 5) этот метод может быть сравнительно просто реализован на комбинационных схемах различной степени интеграции . Он полезен в ситуациях, когда желательно иметь в явном виде локаторы искаженных символов. Такая ситуация возникает, например, при использовании кодов Препараты в качестве подходов в составных кодах .

Во втором методе для каждого символа принятого слова вычисляется значение некоторой функции и по результатам вычислений принимается решение о правильности символа. Однородность вычислений позволяет эффективно реализовать алгоритм декодирования на больших интегральных схемах. Этот метод декодирования состоит в следующем. Пусть принято слово у' = у + В, где у = (а0,а1,..., а1,ь0,ь1,...,ъ11.Л5 кодовое слово кода Препараты, в = (60,6^ — .е^.вд.е^,___,е-[) - слово-ошибка.

Вычисляется синдром в = (в.,, в^, ¿а, йь ) , где

X 1

в, = о0 + о, , вэ = о + о03, аа = ^ а. , ^ = V ъ- (

1=0 . 3=о

°о = I 4di> = 2 bá '0 = I + 2 bó-• i=0 j=0 i=0 j=0

локаторы dj, символов ьд. являются элементами GF(2m), с£0 = р0 = оГ rf^ * d¡2 при i1 * i2; * Í3¿2 при * Зг .

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

Для всех символов левой половины слова у', т.е. для символов a¿,a1',...,a^, решение принимается на основании анализа равенства

( s, i х )3 = о + х3 + í fx) ,

Г

Га(х) = \

о03 , если da = db = о

[ ( о0 + х )э , в противном случае .

Если при х = о^ равенство выполняется тождественно , то символ = 1, в противном случае е^ = 0 .

Для вссх символов ггоавой половины слова у', т.е. для символов г^.ъ.,'.....!),', решение принимается на основании анализа равенства

( б. : х )3 = о + х3 + Гь(х) , ■ '

Гь(х) = j

а^ , если da = db

( o1 + х )3 , в противном случае

Если-цш х = Э^ равенство выполняется тождественно" , - то символ е^ = 1, в противном случае е^- = 0 .

В § 3.4 анализируются методы параллельного декодирования на комбинационных схемах двоичных кодов БЧХ с минимальным расстоянием 8.

В § 3.5 рассматривается параллельное декодирование кодов Геталса. Двоичные нелинейные коды Геталса с минимальным расстоянием & = 8 имеют на два проверочных символа меньше, чем расширенные коды БЧХ с теми же расстоянием и длиной п ( п = 2т+1, т = 21;+1, 1; > 2 ). Известно несколько различных описаний кодов Геталса. Здесь используется описание этих кодов, принадлежащее Бейке-ру, ван Линту и Вильсону (1983г.).

Пусть т = 2t + 1, г = г'1-1 + 1, 5 = 2*+ 1, 1; > 2 - целое.

Пусть у' = у + в = (а|.....,Ьр,Ь.|,... ), V = (а0,

а1,... ,а1 >Ь0,Ь1,... ) - кодовое слово кода* Геталса, в =

г

(е0,е1....,е1,Е0,е1.Ej) - слово-ошибка веса w(e) < 4, v^ = v^

+ е.-, vi = v.. I с. . J- J i> J

Локатовы c^, ß^ символов aif b.. являются элементами

GP(2m) , fl£0 = ß0 = 0 , * Щ)И -i^ ^ i2; ß.^ ß^ при

з1 * 32 •

Синдромом слова v' называется набор s = (S., ,sr,ss,da,db),

где

S1 = °o + °1 • ' sr = °г + °0Г • Ss = °s + °0 '

ill 1

da 2 4- db = 1 b3 ' °0 = I 4 di ' °1 = I b3 03 ' i=0 3=0 i=0 3=0

11 11

о = У a! d.T +' У b'. ß.r , о = У a-' d.s + У b'. ß.s , г L 1 1 L 3 ' s L l X L о *

i=0 3=0 i=0 3=0

Синдром s^ кодового слова v равен нулю, т.е. si0^ = в»>- S<°> = 0, df> = d<°> = 0 .

Лемма. 3-5.1. Если синдромы s^ и s^ слов v^ =

( a<1>, ai1).....a<4 b£ >, b? > ) И = ( a<2>,

.....a(|\ b}25,..., b<2> ) равный а,Г' = ai

(3) = я(1) l

-(2) d _ d (1) 0(1) _ va1 Ь к(Э) _ b(D . ai ' ®k H + °0 • °0 " L ai ai < ь3 ~ 3

i=0

bj2> ; 1,3, k = 0,1,...,1, то v(3) = ( а <3) a«),..., af^)

b|3\..., ь|3Ь - кодовое слово кода Геталса .

Правая половина слова v^) является суммой правых половин слов v^ и v^ , левая половина слова v^) является "сдвигом " ( перестановкой символов ) суммы символов левых половин слов v^1^ и v^K

Следствие леммы 3.5.1. Различные ошибки веса w(e) < 3 имеют различные синдромы.

В силу нелинейности кода Геталса, синдром s^ слова-ошибки е, вообще говоря, не равен синдрому s слова v' = v + е,. где v - кодовое "слово. Однако, db> = S-| '• Кро-

ме того, если ошибки произошли только в правой половине слова, то s^ = Sr и Sg®' = б«.. Если же ошибки произошли только в левой половине слова v\ то s^ = S^, где S^ = Su+ oQu+ о.,и; u = г,б.

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

Наиболее интересным для применений в полупроводниковой памяти является укороченный (49,32У-код Геталса. Для этого кода 1 = 2, г = 3, 8 = 5, т = 5.

Параллельный алгоритм декодирования (49,32)~кода Геталса методом подстановки состоит в следующем .

При ненулевом синдроме одновременно с анализом ошибок осуществляется параллелльная подстановка локаторов символов слова у' в проверочные соотношения.

Локаторы символов а| подставляются

где , о А д

или

1) при <1а. = 1, = 0 в уравнение

з1 15 +.' ьз + (Б3 + ь3 )2 = о ,

а) Ь3 = Б3 + °0 х2 + х , ъ5 = Б5 + о0 X4

б) ь3 = + X3 Ь5 = Б^ + х5 ;

2) при ¿а = V = 0 в уравнение

где

( 2 )3- + х_3 + = 0 ;

3) при йа = аь= 1 в уравнение

( х + о1 )3.= 5Э + Б.,3 + о.,3 ;

4) при <1а = О , аь = 1 в уравнение

( Б.,3 + (о.3 + х)3 + 53 )5 = ( Б.,5 +■ (О,5 + х)5"+ Б5 )3.

Локаторы символов ь^. подставляются

1) при ая = 1, & = о в уравнение

( Б^3 + (О03 + х)3 + )5 = ( Б.,5 + (О05 + х)5 + Б^ )3;

2) при й- = о, йк = 1 в уравнения

э. и

+ 31 Ц + (-Б3 + Ц)2 = О ,

а) Ц = Б^ + 01 у2 + о^ у , Ц = + о1 у4 + о^ у , 0) Ц = Бз + у3 , Ц = + у5 ;

3) при. йа = йь= о в уравнение

.( у + г.,)3 + у 3 + бэ =

4) при ¿а = аь= 1 в уравнение

( у + а0)3 = ^з + + °о •

Локатор ошибочного символа (при числе ошибок в слове у' не более трех) удовлетворяет одному из приведенных выше уравнений .

Если

1) при аа = аъ= 1

( з3 + Б.,3 + о;,3 )5 * ( Б5 + Б,5 + о.,5 )3 ,

2) при <1а = йь= о

и5 + 5,3 пэ + ( Б.,3 * из )2 * 0 ,

где = 53>. и5 = б5 или и3 = и5 = , то считается , что в слове у' обнаружена четырехкратная ошибка .

Полупроводниковая память высокопроизводительных ЭВМ строится в большинстве случаев на больших интегральных схемах (БИС) памяти с одноразрядной организацией.

При одноразрядной организации в БИС памяти каждый такт записывается или считывается из нее один бит. В какдой микросхеме размещается один разряд машинного слова. Любая неисправность одной из БИС памяти с одноразрядной организацией приводит не более чем к одной ошибке в любом машинном слове.

На плате размещаются БИС памяти, содержащие ъ разрядов машинного слова . В полупроводниковой памяти высокопроизводительных ЭВМ чаще всего ь = 4,5,8 или 9 .

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

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

В § 4.1 и § 4.2 рассматриваются алгоритмы декодирования двоичных нелинейных кодов Нордстрома-Робинсона и Препараты, позволявшие исправлять двойные независимые ошибки и одиночные байты ошибок длины 4.

Возможность исправления одиночных байтов ошибок длины 4 в слове у= (а0,а1,... ,а1,ь0,ъ1,... ,Ь1) кода Препараты обеспечивается выбором локаторов и (3.. символов а^ и ь^.; 1,3 = 0,1,...,1 соответственно.

Обозначим

й1а =

ьоно Ь11г2 1ггьз

Н1Н2

Н1Н2

Н1Н2

Н1 Н2

Н1Н2

г1Ъ

н1 ц

1*2

Н1Н1

4-1 ч

Н2 ^

Н1Н1

где

Н1 =

00 01

Н2 =

11

01

Н2 =

11 10

^ - двоичный вектор-столбец длины т-2 векторное представление ненулевого элемента поля

( -брег®-2)

лля 1 = 1,2,...,

г18"2 - 1

и нулевого элемента= о для 1 =

о,ч!~ примитивный элемент СР(2т 2)), I = 2т~2

1

Здесь т > 3. Исправление байтов ошибок длины 4 (1б,8)-кодом Нордстрома-Робинсона (случай т = 3) рассматривается особо..

Двоичные представления матриц Н,

2т различных столбцов, которые-можно рассматривать как векторные представления элементов с? (2го) . Поэтому можно положить

Н1а = Г «О «1 *2 " " ' ] 11 Н1Ь = [ ^ 02 • ' • 01 1 •

Яри применении в полупроводниковой памяти коды Препараты при т > 3 , как правило, укорачиваются. При укорачивании кода для упрощения декодирования символы с нулевыми локатора!® исключаются

1а

Н1Ъ имеют п> строк и

из кодового слова. Набор локаторов слова V

( а^, > ■ * • *

Слово

) укороченного (п,к)-кода: сС1, с£2,..., с^ , р1,

, + 12 = п . V = ( а^, а2,..

V Ь2-

следующим

Ь1 > 1г

Чр-2* а4р-1* а4р' а = 1,2,..-

образом разбивается на байты длины 4 : аДр_

Р = 1,2.....Г V4 1 И Ь4ч-3' Ъ4д-2'

.,1,2.....Г 1р/4 1 . где Г с 1 - наименьшее целое, большее или

равное с . При 11/4 или 12/4 не целых, последние байты имеют длину, меньшую четырех.

Байт ошибок в слове V' - это любая совокупность ошибок в одном из байтов. Байты ошибок веса 1 и 2 исправляются основным

алгоритмом, рассматриваемым в § 3.3, точно так же как и все комбинации независимых ошибок веса 1 и 2 .

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

Алгоритм исправления байтов ошибок состоит из следующих шагов.

. 1. Вычислить синдром б = ( Б.,, б^, йа, аь ) входного слова у' = .Ъ^ ... ,Ь-[ ) ( т'=>+ в , V - кодовое

слово, в = (е^^е^.....е^ ,£^£2« — )- слово-ошибка ).

2. Если синдром Б слова V' равен нулю , то V' - кодовое слово кода Препараты.

3. Если <1а = 1, йь = О, * Б3 г Б^ = о + о^ и г(а) _ З3 + то в слове V' имеется байт ошибок е4р_3, е4р_2, е4р-1' е4р Вбса 3* ^^вой символ = о в этом байте имеет локатор а4р_х = б1 .

4. Если а =0, ей, = '1, б? * в,, б? * бд, бд = о + о? и ш о а о I л ( з з [

г<3 ~ + Б3' то в СЛ0Ее 1,1 имеется байт ошибок едд.з» е4Ч-г' е4д_1» е4Ч в®са 3- Нулевой символ е4с}_.. = о в этом байте имеет

локатор = Б* .

5. Если <1а = ¿ь = О, Б1 = О, Б3 * О и ' = Б^, то в слове у' иглеется байт ошибок е4р_з. е4Р_г' е4р-1' е4р веса

6. Если йа = с1ь = о, б1 = о, Б3 ?! о и = Бэ, то в слове V' тлеется байт ошибок е4с}_2, е4д_1» е4Ч 4.

Для (1б,8)-кода Нордстрома-Робинсона доказывается следующая

Лемла 4.1.1. Пусть у = (а(?,а1,... ,а7,Ъ0,Ь1,... ,Ъ7) - кодовое слово кода НР , 0, и $ - локаторы символов ао,ьО' ■ а7"-1 и ь7-«' соответственно, х,а = 1,2,...,7. Тогда в слове у = (. а0,а7,ь0,ъ7> а1,а2,а3,а5, а4,а6,Ъ2,Ьэ, Ь^Ь^,bj.bg ) эквивалентного кода могут быть исправлены наряду с одиночными и двойными независимыми ошибками одиночные байты ошибок длины четыре.

Прямую сумму двух произведений кодов будем называть составным кодом. В § 4.3. рассматриваются составные коды, исправляющие двойные независимые ошибки и о даточные байты ошибок, и алгоритмы их декодирования. В отличие от кодов, описываемых в §§ 4.1,4.2, составные кода могут исправлять байты ошибок различной длины.

Пятая глава посвяшенз самопроверяющимся алгоритмам и схемам

А 19

кодирования и декодирования линейных кодов.

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

Эффективным средством обнаружения схемных ошибок являются самопроверяющиеся схемы. Для сравнительно простых кодов (например, кодов Хэмминга) самопроверяющиеся схемы могут строиться непосредственно. Для более сложных кодов (например, двоичных кодов БЧХ или кодов Рида-Соломона) представляется полезным сначала построить самопроверяющийся алгоритм декодирования, а уже затем на его основе 'строить самопроверяющуюся схему декодера.

В § 5.1 анализируются модель алгоритмических ошибок и модели ошибок комбинационных схем. __

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

Пусть алгоритм А состоит из последовательности шагов (подалгоритмов) .....А . Подйлгоритм' А± отображает множес-

тво X входных последовательностей алгоритма А в множество Y^ выходных последовательностей подалгоритма А^ .

Множество одиночных ошибок F алгоритма А можно представить как р = Р1 и Р2 и-.-и где множество одиночных ошибок подалгоритма А^. Выходная последовательность у! = ф^х,^), tFj подалгоритма Ai может не совпадать с выходной последовательностью yi= ср^хД) , получающейся в отсутствии ошибок (¡\. обозначает нулевую ошибку).

Подалгоритм А^ алгоритма А называется самопроверягацимся (защищенным от ошибок) для множества входных последовательностей X алгоритма А и множества ошибок Fj подалгоритма Aiw если для любых х 6 X и х±£ Fi либо yl = yi , либо у| g Yj.

Введем функцию называемую анализатором безошибочности .(реализации) подалгоритма Функция может принимать одно' из двух значений: 0 или i. Для любой входной последовательности х £ X алгоритма А й любой ошибки fPj функция = 1, если выходная последовательность у| £ Y^, и Ф^ = О , в противном случае .

Анализатор безошибочности Ф алгоритма А , состоящего из

1 '.20^1

последовательности шагов (подалгоритмов) /Ц,^.....^ , равен Ш

= v í>2 ------ ®г

Пусть С - комбинационная схема с N входами и м выходами. Схема С однозначно (в отсутствие ошибок) отображает множество х входных последовательностей х =(х1,х2,...,хк), 0,1; i =1,2, ...,N в множество Y выходных последовательностей у = (У1.У21->-.Уи)> Уд= 0,1; ó =1,2,...,м.

Предполагается, что в схеме С могут происходить ошибки из множества F. В дальнейшем р - это множество всех одиночных ошибок.

Если в схеме С произошла ошибка г £ F, то выходная последовательность у '= (p(x,í) может не совпадать с выходной последовательностью у = ф(х,Я), получающейся в отсутствие ошибок.

Наряду с известными понятиями полностью самопроверяющихся и самотестирующихся комбинационных схем (детальное описание свойств таких схем можно найти, например, в книгах Вэкерли (1978 г.) и Pao и Фудзивара (1989-г.)) вводится понятие полностью самопроверяющейся комбинационной схемы с минимальной задержкой тестирования X (ЛгО).

Пусть Fu - подмножество множества всех одиночных ошибок Р, состоящее из и элементов, 1 < и < п и í* = Fn .

Обозначим через С(F ) схему, получающуюся из схемы С в результате действия (в любой последовательности) множества ошибок т.е. С(РЦ) - это схема, в которой имеется и-кратная (постоянная) ошибка, состоящая из ошибок множества Fu .

Пусть y(x,Fu) и у(х,Л.) выходные последовательности схем C(FU) и С соответственно.

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

Определение 5.2.1. Схема С называется вполне защищенной от подмножества ошибок Pq, Fq £ F = Fn , 1 < q < n , если

1) для любого Рр , Fp с Fq и любого х £ X имеет место у(х,Рр) = у(х,\) ;

2) существует х' £ X такое, что y(x',Fq) Ё Y ;

3) для любого х £ X, х * х' либо y(x,Fq) = у(хД), либо yU,Pq) & Y .

Подмножество ошибок Pq , от которого схема С вполне защищена, будем называть вполне тестируемым. Будем говорить, что ошибка íj £ F схемы С тестируема с минимальной (максимальной) задержкой A-i, если ?„ минимальное (максимальное) вполне тести-

руемое подмножество, содержащее ti , и = q^ - 1.

Определение 5.2.2. Схема С называется полностью самопроверяющейся схемой с минимальной задержкой тестирования А, для множества входных последовательностей X и множества ошибок F, если

1) любая ошибка fi £ Р тестируема с минимальной задержкой

А. . и гаах А. . = А, ; 1 l^e Р 1

2) для любой ошибки f^ £ ? и любого собственного подмножества

ошибок Р минимального вполне тестируемого подмножества F , pi

содержащего f., схема 0(р ) защищена от ошибок для множества

входных последовательностей X и множества ошибок F.

Полностью самопроверявдаяся схема имеет минимальную задержу тестирования А = 0.

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

В § 5.4 строятся и исследуются самопроверяющкеся алгоритмы декодирования двоичных кодов БЧХ.

Пусть v - линейный двоичный код с проверочнойй матрицей н и минимальным расстоянием d = 2 t + 1 - Пусть ъ' = Ъ + е, b - кодовое слово кода т, е - слово-ошибка и алгоритм декодирования Ау кода v состоит из следующих шагов :

1. Вычислить синдром S = ъ' нт.

2. По синдрому s найти слово е* наименьшего веса такое, что S = е* Нт.

3. Вычислить Ьс„_ = Ъ' - е*.

allA.

Если вес w(e) < t , то алгоритм Ау находит переданное кодовое слово ь = ьвшс .

Множество У выходных последовательностей алгоритма Ау состоит из слов кода v и, вообще говоря, алгоритм не обязательно является самопроверяющимся. Наряду с ьвых будем вычислять слово

ьвых = ьвых ~ ь* СЧ11ТЗТЬ выходом алгоритма пару (ьВых,ъвых^ Тогда у = { у = (Ьшх,ь^ых): 3(ьвых) = О, иь^д) < t } и алгоритм Av становится самопроверяющимся.

Для кодов БЧХ предлагается более эффективное решение. Пусть V - двоичный циклический (п,к)~код БЧХ с конструктивным расстоянием d = 2t + 1 и порождающим многочленом g(x) = НОК

I М(1)(7.}, ?.'(3)<:-:>.....M(2t-1)(x) }, где li(1)(x) - минимальный

многочлен элемента а1, ä - примитивный элемент GF(2n).

Рассматривается алгоритм декодирования двоичного кода

БЧХ с конструктивным расстоянием d = 2t + 1 , состоящий из следующих шагов.

1 .Вычислить для многочлена b'(z) , соответствущего слову

2+-1

b'=(b.[,b^.....ь^), многочлен S(z) = £ s^z3' , s^. = b'^41).

3=0

2.Применяя расширенный алгоритм Евклида к многочленам и S(z), определить многочлен локаторов ошибок alz) степени < t.

3. Найти корни многочлена o(z).

4. Найти локаторы и позиции ненулевых символов слова-ошибки в = (е^.eg,...>8П)-

5. Вычислить bRHT = b'. - е .

Сначала рассматривается построение анализатора безошибочности алгоритма как функции выходного слова ЬБЫХ алгоритма.

Лемма 5.4.3. Одиночная ошибка при реализации алгоритма для любого входного слова Ъ' = b + е, w(e) < t может привести только к такому выходному слову bBKX, что вес "(Ъвцх - b) < 2t.

Лелик 5.4.4. Для простого р , целых m > 1, t > о и q - pm, удовлетворяющих неравенству (q-1 ) (q-2)... (q-t) > q^-1 - q1*-" , существует пара многочленов a(z) и bis) над GF(q) степени t ,

г

a(s) = s + a^s + ... + . at_1z + a^, at * О

11 - t t-l

b(z) = z + b^z + ... + . bt_1z + bt, bt * 0,

не имеющих кратных корней и полностью разлагающихся в gf(q) на линейные множители, и вес w(a(z) - b(z)) = 1.

Лелла 5.4.5. Одиночная ошибка при реализации алгоритма для любого входного слова b' = b + е, w(e) < t может привести к выходному слову ьшх такому, что "(ЬЕЫХ ~ b) =

Теорема 5.4.1. Алгоритм является самопроверяющимся и

функция 1])^,

ф _ I о, если синдром s(bEUX) = о, 2 t 1, в противном случае, является анализатором безошибочности алгоритма ¿Sgq^

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

В § 5.5 рассматриваются самопроверяющиеся алгоритмы и полностью самэпроверяющпеся схемы кодирования и декодирования двоичных кодов БЧХ с минимальным расстоянием 6.

При рассмотрении Еопроса о самотестируемости комбинационных схем декодера существенно используются следующие леммы.-

Аемла 5.5.2. Для нечетного m и любого элемента (3 поля GF(2m) найдется слово ь* = ъ + в' , где ь - кодовое слово (n,k)~ кода БЧХ с минимальным расстоянием d = 6 и к > 2т~1 , е' -слово-ошибка веса w(e') < 2 , такое ,что 0 = S., , и слоео ь" = Ь + в" , w(e") < 2 , для которого ß = Sg .

Аелла 5-5-3. Для любых ßj, | £ G?(2m) найдется слово b* = b + е', w(e') = 2 такое, что ( S1 + ß^ )3 + S3 + ß? = % .

В §_ 5.6 рассматриваются самопроверящиеся комбинационные схемы кодирования и декодирования двоичных кодов Хэмминга -с млни-мальным расстоянием d = 3. Эти коды используются в БИС памяти при построены! встроенных схем исправления ошибок .

Показывается, что для укороченных кодов Хэмминга нельзя построить полностью самоправеряидуюся схему декодирования, но можно построить близкую к ней по своим свойствам полностью самопроверя-кцуюся схему с минимальной задержкой тестирования X , 0 < X < г.

Теорема 5.6.1. Для неукороченного (2г-1,2г-г-_1 )-кода Хэмминга с минимальным расстоянием d = 3 может быть построена полностью самопроверяющаяся сеть с кодовым обнаружителем ошибок, состоящим из полностью самопроверяющегося вычислителя синдрома выходного слова декодера d .

Теорема 5-6.2. Для укороченного (п,к)-кода Хэмминга (п < 2г-1) с минимальным расстоянием 4 = 3 :

1) не существует полностью самопроверяющегося комбинационного декодера ъ% ;

2) при n > 21""1 может быть построен полностью самопроверяю-иийся декодер с минимальной задержкой тестирования X, X < г ;

3} при п > г1--1 существует проверочная матрица н кода Хэмминга такая, что может быть построен соответствующий матрице н полностью самопооверяннийся декодер Dx с минимальной задержкой тестирования X = 1;

4) полностью самопроверяюшийся кодовый обнаружитель ошибок полностью самопроверявдегося декодера Dx с минимальной задержкой тестирования X состоит из полностью самопроверяющегося вычислителя синдрома выходного слова декодера.

В главе 6 рассматриваются вопросы, связанные с использованием модифицированного кода Хэмминга в основной полупроводниковой памяти суперЭВМ " Электроника СС БИС ".

В § 6.1 рассматриваются свойства и способы построения однородных проверочных матриц (72,64)-кодов Хэмминга, позволяющих построить максимально быстрые кодер и декодер, а также наряду с

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

В § 6.2 описывается структурная схема декодера, приспособленного для реализации на ВИС. В § 6.3 исследуются свойства и способы построения полностью самопроверяхшдахся кодеров и декодеров модифицированного кода Хэмминга .

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

В главе 7 рассматриваются параллельно-последовательные и параллельные алгоритмы и схемы кодирования и декодирования составного (80,64)-кода, используемого для исправления двойных независимых и байтов ошибок во внешней полупроводниковой памяти суперЭВМ " Электроника СС БИС ".

В § 7И описываются структура и алгоритм кодирования составного (80,64)-кода.

Пусть г1 - линейный (1б,14)-код Рида-Соломона над СР(24) с минимальным расстоянием <ц = 3, 22 - двоичный нелинейный (16,8)-код Нордстрома-Робкнсона с минимальным расстоянием с^ = б.

Обозначим через [х] - двоичный каскадный код, являющийся произведением внутреннего двоичного (5,4)- кода V., с проверкой на четность и внешнего (1б,14)-кода Рида-Соломона над СР(24) . Пусть У = V, » т2 - линейное 5-мерное пространство и уг ® 22 ~ итеРатиЕНЫЙ двоичный код.

Множество слов, являющихся всевозможными суммами слов кодов X = у1 [х] и У = Уг в г2, образует нелинейный составной код V. Параметры кода V : длина п = 80, число информационных символов к = 64, минимальное расстояние <1 = 6. Код V образует обобщенный каскадный код второго порядка и это используется в алгоритме кодирования.

В § 7.2 рассматривается параллельно-последовательный алгоритм декодирования, в котором слова кодов Рида-Соломона и Нордстро-ма-Робинсона декодируются параллельно так, что для каждого кода последовательно находятся локаторы ошибок, ненулевые символы слова-ошибки и выходное кодовое слово.

Более быстрым, но требующим при реализации большего количества логических схем является параллельный алгоритм декодирования составного (80,64)-кода, рассматриваемый в § 7.1.3 . При параллельном алгоритме слово кода Кордстрома-Робшсона выделяется из сос-

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

В этом же парагра£е показывается, что оба алгоритма декодирования составного (80,84)-кода позволяют исправлять кроме двойных независимых ошибок одиночные байты ошибок длины 4 и 5.

В § 7.4 описываются структуры комбинационных БИС и СБИС кодера и декодера (80,64)-кода.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

Основные результаты и выводы работы состоят в следующем :

1. Введена метрика, описывающая декодирование по минимуму обобщенного расстояния Форни, и на ее основе предложен общий подход к построению алгоритмов декодирования произведений кодоб.

2. Исследованы свойства и построены алгоритмы декодирования прямых суш произведений кодов.

3. Исследованы свойства и разработаны конструкции линейных кодов с неравной зашитой информационных символов.

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

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

5. Построены элементы теории самопроверяющихся алгоритмов декодирования линейных кодое. Разработаны и исследованы самопроверяющиеся алгоритмы декодирования кодов БЧХ, исправляющих многократные ошибки.

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

6.Построены полностью самопроверяющиеся схемы кодирования и декодирования кодов лэмминга с минимальным расстоянием <1 = 3, модифицированных ко дев лэмминга с л = 4, кодов БЧХ с <1 = 6.

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

Результаты диссертации опубликованы в следующих работах :

1. Еояринов И.М. О кодах с неравной защитой символов /Тр. V конф. по теории кодирования и передачи информации. Тез. докл. Горький. М.: Наука. 1972. С. 22-24.

2. Бояринов И.М., Кацман Г.Л. Линейные коды с неравной защитой информационных символов // Вопросы кибернетики. Проблемы избыточности в информационных системах. М.: ВИНИТИ. 1977. С. 60 - 91.

3. Бояринов И.М., Канман Г.Л. Две конструкции кодов с неравной защитой символов от группирующихся ошибок // VII Всесоюзная конференция по теории кодирования и передаче информации. Доклады. Часть II. Теория помехоустойчивости кодирования. Москва-Вильнюс. 1978. С. 15 - 19.

4. Бояринов И.М., Кацман Г.Л. Класс оптимальных двоичных линейных кодов с неравной защитой информационных символов //.Труды V Международного симпозиума по теории информации. Тезисы докладов. Тбилиси. М. : Наука, 1979 . 4.1. С. 56 - 58 .

5. Бояринов И.М.Об исправлении ошибок прямыми суммами итеративных и каскадных кодов // Доклады АН СССР . 1980. т. 252. № 3. С. 563 - 565.

6. Бояринов И.М. Об одной конструкции линейных кодов с неравной защитой информационных символов // Проблемы передачи информации. 1980. т. 16. & 2. С. юз -107.

7. Бояринов И.М. Метод декодирования прямых сумм произведений кодов и его применение // Проблемы передачи, информации. 1981. т. 17. И 2. С. 39 - 51.

8. Boyarinov I.M., Katsman G.L. Linear unequal error protection codes // IEEE Trans. Inform. Theory. 1981. v. 27. * 2. P. 168 - 175.

9. Бояринов И.М. Комбинированные методы декодирования линейных кодов с неравной защитой информационных символов // Проблемы передачи информации. 1933. т. 19. Я 1. С. 21 - 29.

10. Бояринов И.М. Помехоустойчивое кодирование числовой информации / М.: Наука. 1983.

11. Анохин A.B., Бояринов И.М., Давыдов A.A., Дадаев Ю.Г., Салакатов В.П. Исправление двойных и обнаружение тройных ошибок в полупроводниковой памяти ЭВМ // Вопросы кибернети-

кн. Проблемы создания высокопроизводительных ЭВМ. М.: ВИШ-ТИ, 1984. С. 50 - 66 .

12. Анохин A.B., Бояринов И.М., Давыдов A.A. Методы параллельного декодирования кодов БЧХ, исправляющих двойные и обнаруживающих тройные независимые ошибки // Вопросы кибернетики. Проблемы организации высокопроизводительных ЭВМ. М.: ВИНИТИ, 1984. С. 48-92.

13. Анохин A.B., Бояринов И.М., Давыдов A.A. Быстрое кодирование и декодирование (16,8)-кода Нордстрома-Робинсона // Вопросы кибернетики. Проблемы создания высокопроизводительных ЭВМ. IL: ВИНИТИ, 1934. С. 66 - 80 .

14. Анохин A.B., Бояринов И.М., Давыдов A.A., Дадаев Ю.Г., Мельников В.А., Митропольский Ю.И., Салакатов В.П., Улыбин Ю.Е., Воробьев P.M.'Устройство для кодирования 64-разрядных информационных слов в составной корректирующий код с расстоянием 6 // Авторское свидетельство. № 1132292. 1.9-1984.

15- Анохин A.B., Бояринов И.М., Давыдов A.A., Дадаев Ю.Г., Меле-шкшЮ.Н., Мельников В.А., Митропольский Ю.И., Салакатов В. П. Устройство для декодирования составного корректирующего кода // Авторское . свидетельство. № 1229SS9. 8.1.1936.

16. Бояринов U.M. О систолических и полусистолических вычислениях в GF(2a) // Вопросы кибернетики. Разработка и использование супер-эв?.!. М.: ВИНИТИ. 1937. С. 183 - 191.

17. Анохин A.B., Бояринов И.М. Параллельный алгоритм исправления двойных независимых и одиночных байтов ошибок в полупровод-киковой памяти супер-ЭВМ / I Всесоюзная конференция " Проблемы создания супер-ЭВМ, суперсистем и эффективность их применения ". Минск. 1987. Тезисы докладов. Часть 2. С. 115 -117.

18. Бояринов И.М., Давыдов A.A., Шабанов Б.М. Исправление ошибок в основной памяти высокопроизводительной ЭВМ // Автоматика и телемеханика. 1987. № 7. С. 152 - 165.

19. Бояринов И.М. Параллельное декодирование кодов Препараты // Вопросы кибернетики. Эффективные вычисления на супер-ЭВМ. М.: ВИНИТИ. 1988. С. 170 - 179.

20. Boyarinov I.Ii. Seli-checking parallel decoders for the Pre-parata codes // II International Workshop " Algebraic and Combinatorial Coding Theory ". Abstract of papers. M.: 1990. P. 42 - 44.

21. Boyarinov I.M. Self-checking decoders for computer semiconductor memory // Fifth Joint Soviet-Swedish International Workshop on Information Theory. Moskow. 1990. P. 34 - 37.

22. Анохин A.B., Бояринов И.М. Исправление одиночных байтов и двойных независимых ошибок в полупроводниковой памяти суперЭВМ // Вопросы кибернетики. Базовое программное обеспечение суперЭВМ. U.: ВИНИТИ. 1990. С. 174 - 190.

23. Бояринов И.М. Самопроверяющиеся и самокорректирующиеся схемы декодеров кодов, исправляющих: одиночные байты ошибок // Автоматика и вычислительная техника . 1991. И 3. С.Ю4 -109.

24. Бояринов И.М. Самопроверяющиеся и самокорректирующиеся кодеры и декодеры для основной полупроводниковой памяти суперЭВМ // Вопросы кибернетики. Прикладное программное обеспечение и и моделирование суперсистем. М.: ВИНИТИ. 1991. С. 136-151.

25. Бояринов И.М. Исправление многократных ошибок в полупроводниковой памяти ЭВМ // Вопросы кибернетики. Средства моделирования и разработка прикладных программ для суперЭВМ. М.: ВИНИТИ. 1992. С. 132 - 161.

26. Бояринов И.М. Полностью самопроверяющиеся и самокорректирующиеся БИС кодеров и декодеров модифицированных кодов Хэммин-га // Микроэлектроника. 1993. т. 22. вып. 3. С. 23-36.

Тираж 100 экз.