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

Введение к работе

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

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

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

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

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

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

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

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

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

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

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

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

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

Построены полностью самопроверяющиеся схемы кодирования и декодирования кодов Хэмминга с минимальным расстоянием а = 3, модифицированных кодов Хэмминга с d = 4, кодов БЧХ с d = 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 г.), Щербакова (і989 г.), Рао и Фудзивары (1989 г.).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ОСНОВНОЕ СОдЕРНСШ РАБОТЫ

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

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

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

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

Теперь предположим, что о каждом символе у. слова у =
(у.рУ2>--->У_п) имеется дополнительная информация, выражаемая
числом $у', 0 < р^^у' < 1/2, называемым коэффициентом недосто
верности символа у_А , і = 0,1,...,n . Стертым символам, если
таковые имеются в слове у , присваивается наибольший коэффициент
недостоверности, равный 1/2. Будем считать, что все символы лю
бого слова кода z имеют коэффициент недостоверности, равный
нулю. Таким образом, каждому слову у = (у,,у~,...,у„) с симво-
лами из алфавита П ставится в соответствие вектор $' =
(0^.0^,....0^), 0 < (3}^У> < 1/2, 1 = 1,2 п. _

Пусть даны два слова у = (у_гу₂,...,у_п> и z = (s *z₂,:..,s_n) с векторами недостоверности р'^у* = (0}^у\0|^у\...,0^^у^) и ^^z' = (0j^z',0₂ .---.Зд ) соответственно. Пусть |а| - модуль а и

п Г |0^^у) - р|^а)!, если у^_ = z_v

i=i [ 1 - ірї^у:> - p|^s)|, если у^

d₀(y,z) = 2 Ф_х , Ф_А = {

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

Общий летод декодирования б обобщенной метрике. Для опреде
ления по слову у = (у.,, у₂,..., у ) и его вектору недостоверно
сти 0^(у' = (0^,(3^ ^п⁷^ кодового слова z = (z₁,z₂,...,

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

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

Упорядочим символы вектора 3^^у' в виде убывающей последовательности, добавив к ним Ш^у' такое, что pi^y' > (3;^у^ , :

е<у> > р(у) > ... > й<^у> > ... > й<^у> > р<У> . И ^х2 ^хш -"-п ^хп+1

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

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

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

где в_т - число нестертых позиций, в которых у^^т' и z различаются. С помощью алгоритма исправления ошибок и стираний по слову у^^т' на этом шаге определяется кодовое слово z .

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

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

UQ(y,z) < d/2 .

-Кроме того, не нужно делать все n + 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 г.), Лином 3. и Лином- Ш. (1990 тґгг а также в работах [1-Ю], часть результатов которых использована в данной .главе.

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

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

Будем говорить, что і-й информационный символ (1-й символ информационного слова) кода У имеет степень защиты і^, если какие бы t it < x_i) ошибок не произошли в произвольном кодовом слове ь, этот символ определяется верно при декодировании слова ъ' = ь + е, w(e) .= і в ближайшее к нему кодовое слово.

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

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

Лелла 2.1.4. Для того чтобы к" информационных символов линейного (п.к)-кода v имели степень зашиты б, необходимо и достаточно, чтобы код v разлагался в прямую сумму v = V V" такую, что размерность V" равна к" и все слова v v веса не более 2Q принадлежат V .

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

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

Теорела 2.2.2. Пусть m и t - целые числа такие, что (2t - 1, 2<л»_ 1) = 1 , t > 3 . Тогда линейный двоичный (п.к)-код v_t с проверочной матрицей H_t ,

1 о ... о |3 ... о

^Ht=

;t-3

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

1 о ... о

_d2t-1 _ _ _rf(2t-1)2^m _й(2і-1)(2^т+1) _d(2t-1)(2^m-2)

где d - примитивный элемент GF(2^2ffl) и р = ot^{2 +1}, имеет длину п = 2-1, число проверочных символов г < (t + 1 )m, минимальное расстояние d = 3 и эквивалентен линейному систематическому коду 7, в котором не менее чем 2^Ш -(t - Dm -1 информационных символов имеют степень зашиты t.

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

Пусть заданы две последовательности линейных кодов. Последовательность v,, v₂,..., V_ffl кодов над Gi4q) такова, что длины всех кодов одинаковы и равны n_v , число информационных символов кода Vj (і = 1,2,...,т) равно к^ , для каждого і сумма v₁ + ?₂ + ... + Vj прямая и минимальное расстояние кода 7^ = v₁ в v₂ в ... eTj равно/ dj_. Последовательность z₁, z₂,..., Z_m кодов такова, что длины всех кодов одинаковы и равны n_z ; Z_i (і = 1,2, ...,m) есть либо код с символами из GP(q) , либо код с символами из GP(q^ki) ; в обоих случаях число ішформацио"ншх символов кода z_i равно к_і, а минимальное расстояние равно D_i. Предположим, что i,D₁ < а^ < ... < «у^. Определим Yj » z^ как произведение кодов Y_i и z_i , понимая под этим тензорное произведение V, в z- , если Z. - код над GP(q) , и каскадное про-

изведение v_i[7j z_i, если Z.. - код над GF(q Ъ .

Теорела 2.3.3. Сумма Y,, « Z₁ + v₂ * Z₂ +...+ V Z_m - прямая ; U = Y₁ * Z₁ в ?₂ » Z₂ e... Y_m » Z_m - линейный (п.к)-код

над GP(q) длины n_n„ с числом информационных символов - к
m m

= J ^кі^Кі ^и минимальным расстоянием с^ > і, D₁ ; w = ^кі^Кі

і=1 i=j

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

б₃ = [(d^ - 1)/21 .

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

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

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

В ВИДЄ u = u, + Uj, + ... + t^ , ГДЄ U є и^, = Y_i I ^, І = 1,..

.,m, декодирование слова и' будем осуществлять в m шагов. На первом шаге по слову и' определим кодовое гід и информационное а_щ слова кода и_т . На втором шаге по слову й^_., = u' - t^ определим кодовое u_m_₁ и информационное а_ю_₁ слова кода D_m_₁ . На і-м шаге по слову

"m-d-D = ^u' - "т-а-г) ~ V-(i~3) ~ " ~ "т

ОПреДеЛИМ КОДОВОв U_m__fi_₁ v И ИНфОрМаЦИОННОе ^am-(i-1) ^слова

кода f_ffl_(і_.|)« Наконец, на т-м шаге по слову й' = и' - ug - ug - ...- i^ определим кодовое и, и информационное а₁ слова кода и., и тем самым кодовое и = о, + Ug + "3 ⁺ ---+ - ^И информационное а=а₁ + ag + ag + ,..+ а слова кода. U .

На і-ом (і = 1,...,т) шаге, декодируя слова-столбцы слова **m-(i-l) с помощью алгоритма декодирования кода v₁, находим для слова *щ_(і-і) вектор недостоверности 0' = (gj,...,0!,...,) ,

Г ^ез ' V(i-1) '^{всш e}j < V(i-1)^/2 '

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

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

По слову 2щ_/.;_]) и его вектору недостоверности |3' с помощью метода декодирования в обобщенной метрике, рассмотренного в 1.1, находим слово *_а_ц_-)\ кода ^z_m-(i-i) такое, что

V^-d-D» ^zn3-(i-i) ) ^{< D}m-(i-D^/2

Теорема 2.3.6. Пусть код и 'удовлетворяет условиям теоремы 2.3.3 и u'=u + E,uU,E- слово-ошибка. Если вес w(E) < б₁ , то m-шаговый алгоритм декодирования кода U определяет истинные значения информационных символов подкода v^ * z^ в . .. в v_m ». z_m кода V . При w(E) < dL₎D₁ алгоритм по и' находит истинное кодовое слово U .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Во втором методе для каждого символа принятого слова вычисляется значение некоторой функции и по результатам вычислений принимается решение о правильности символа. Однородность вычислений позволяет эффективно реализовать алгоритм декодирования на больших интегральных схемах. Этот метод декодирования состоит в следующем. Пусть принято слово у' = у + Е, где у = (a₀,a_1t..., a_l,.b₀,b₁,...,b_ll.^_s кодовое слово кода Препараты, в =

(e_Q,e,,— .є^.Єд.є.]', ,e-J) - слово-ошибка.

Вычисляется синдром в = ( s.,, s,, d_a, d_b ) , где

^S1 = 0 + о₁ , s₃ = о + о₀³, d_a = I a: , d_b = I Ъ* ,

i=0 . j=0

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

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

( s, : х )³ = о + х³ + f (х) ,

Oq , если d_a = d. = О

*«<*> = \

[ -' ( о₀ + х )^э , в противном случае

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

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

( s, і х )³ = о + х³ + f_b(s) , '

о.,³ , если d_a = d_fe = О

I ( o₁ + x )³ , в противном случае

Если-пли х = S. равенство выполняется тождественно" ,- то символ є'. = і, в противном случае е ' = 0 .

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

В 3.5 рассматривается параллельное декодирование кодов Геталса. двоичные нелинейные коды Геталса с минимальным расстоянием d = 8 имеют на два проверочных символа меньше, чем расширенные коды БЧХ с теми же расстоянием и длиной n ( п = г"⁵"¹"¹, m = 2t+i, t > 2 ). Известно несколько различных описаний кодов Геталса. Здесь используется описание этих кодов, принадлежащее Бейке-ру, ван Линту и Вильсону (1983г.).

Пусть m = 2t + 1, г = 2^t_1 ч- 1, s = г*+ 1, t > 2 - целое.

Пусть, v* = v + в = (aj а^.Ь^Ь.,',...,^), v = (a_Q,

a₁,..._Ia_l,b₀,b₁,...,b_l) - кодовое слово кода* Геталса, в =

(e₀,e₁,...,е₁,є₀,є₁,...,Ej) - слово-ошибка веса w(e) < 4, v! = v.

+ e.-, v'. = v.. і c. . і j j j Локаторы d^, (3. символов a_if b. являются элементами

GP(2^m) , o₀ = g₀ = 0 , c^ * ri-₂ при .1^ * i₂; &^ 0^ при

3₁ * 3₂

Синдромом слова v' называется набор s = (S.^S^Sg.c^.djj), где

^S1 = o ⁺ 1 ' ^sr = r ⁺ 0^{Г s}s = s ⁺ 0

ill 1

^da = 14' ^db = 1 ^b'i > 0 = 1 4 *i 1 = I ^bj P₃ -

i=0 j=0 i=0 0=0

о = У a.* d.^T +' У b'. Є.^г , о = У a-' d.^s + У b*. Є Л ,
i=0 j=0 i=0 j=0

Синдром S^^Q' кодового слова v равен нулю, т.е. s}⁰' = s<>= s<>= о, df> = а<> = о .

id) _{w я}(2) -,„» „(і) „

(2) 'О

(а">. а<¹> а<¹>, Ь<¹ >, Ъ<4 .., b<¹ > ) И v<²> = ( а,

^ ) равны и а^ = а|¹ * +

1 а<²⁾ d -Л + о⁽¹⁾ о⁽¹⁾ - ^a⁽¹⁾r* Ь^(Э) - Ь⁽¹⁾ +

i=0 bf ; 1,5,1с = 0,1,...,1, то" v<3> = _{( а}(3) ,(3),..., _а(3)_>ь(3)

b.p',..., bp') - кодовое слово кода Геталса .

Правая половина слова v'³^ является суммой правых половин слов v^¹' и v* ' , левая половина слова v^' является "сдвигом " ( перестановкой символов ) суммы символов левых половин слов V^¹ ' И Ч^К

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

В силу нелинейности кода Геталса, синдром s^ слова-ошибки е, вообще говоря, не равен синдрому s слова v' = v + е,. где v - кодовое слово. Однако, ^- &_а> <^^е - <Ц>» $\^е = S₁ . Кроме того, если ошибки произошли только в правой половине слова, то z^ = S_r и Sg' = s_o. Если же ошибки произошли только в левой половине слова v\ то s^^e' = S^, где S^ = S_u+ o_Q^u+ o^; u = г,б.

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

Наиболее интересным для применений в полупроводниковой памяти является укороченный (49,32У-К0Д Геталса. Для этого кода t = 2, г = з, s = 5, m=5.

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

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

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

1) при d . = 1, d_b = о в уравнение

где или

s₁ i₅ +;s., ь₃ + ( б^ + ь₃ )² = о ,

а) L₃ = s₃ + о₀ х² + Oq ж , ъ₅ = s₅ + о₀ х⁴ +" Oq z ,

б) L₃ = S₃' + х³ , L₅ = S^ + х⁵ ;
г) при d_a = d_b= о в уравнение

( х +-S^)³- + х_³ + Sj = 0 ;

3) при й_а = й_ъ- 1 в уравнение

( х + о\,)³.= S₃ + S.,³ + о.,³ ;

4) при d_a = О , d_b = 1 в уравнение

( S.³ + (о.³ + х)³ + S₃ )⁵ = ( S.,⁵ + (о,⁵ + z)⁵"+ s₅ )³.

Локаторы символов ь'. подставляются 1) при d₌ = 1, d- = о в уравнение

( S.,³ + (о₀³ + х)³ + s₃* )⁵ '= ( S.,⁵ + (о₀⁵ + х)⁵ + Б^ )³; г) при d„ = о, d_K = 1 в уравнения

S₁ Ц + S₁ Ц + (-S³ + Ц)² = о ,

а) Ц = s₃^r + о, у² + о² у , Ц = S + о, у⁴ + о⁴ у , 0) Ц = S₃ + у³ , Ц = S₅ + у⁵ ;

1. при. d_a = d_b= о в уравнение .(y + s,)³ + у ³ + s₃ =

2. при d_a = d_fc= 1 в уравнение

( у + о₀)³ = s₃' + sf + cj* .

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

Если

1) при d_a = d_b= 1

( s₃ + s.,³ + о;,³ )⁵ * ( s₅ + s,⁵ + о.,⁵ )³ ,

2) при d_a = d_b= 0

S₁ U₅ + 5,³ U₃ + ( S.,³ + U₃ )² * 0 ,

где XI, = s,,. u₅ = s₅ или її, = sj, u₅ = si , то считается , что в слове v' обнаружена четырехкратная ошибка .

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

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

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

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

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

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

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

Обозначим

h₀h₀ ь.^ ъ^ъ.₃

^ht-1^ht

^ht^h1

"1а

^Н1^Н2

^Н1^Н2

^Н1^Н2

Н* Но Н- Нр

^h0^h0 ^h1^h2 ^¹ HpHp

EL Нр

^Н1^Н1

^ht-1^ht

^н1 =

_ч

fa^Wj)

. - двоичный вектор-столбец длины m-2 ( w. -векторное представление ненулевого элемента w^x поля GF(2 ' )

ДЛЯ І = 1,2,..., 2^й1"² - 1 И НуЛеВОГО Элемента Wq = о для і =

о , w - примитивный элемент GF(2^m~²)), t = 2 - 1 .

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

строк и

Н_{1 ъ} имеют

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

2 различных столбцов, которые-можно рассматривать как векторные

представления элементов GF(2 ) . Поэтому можно положить

1а

d₀ й,

*г

^Ai

и н.

Зп 3

_-ч-

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

' S-i » &р»

^х1 Pi.

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

Ъ^ ) укороченного (п.к)-кода:

3,

следующим

Слово

h ⁺ h

{ а- , а«,..., a. , D-,

^bl >

v — { а* , а«,..., а

4р-3' ^а4р-2* ^а4р-1' ^а4р'

образом разбивается на байты длины 4 р = 1,2,...,Г 1/4 1 и

^b4q-3' ^b4q-2' ^b4q-1 ^b4q' где Г с 1 - наименьшее целое, большее или

q = 1,2,..

,1,2 Г l₂/4 1

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

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

--18Г-

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

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

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

. 1. Вычислить синдром s = ( s.,, s,, d_a, d_fc ) входного слова v' = (aj,a^,...,a-[ .Ь^.ЬД.,.. .,b-[ ) ( v'='v+ в , v - кодовое

слово, в = <е.,е₂ є, ,е. ,є₂..-->-] )- слово-ошибка ).

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

3. ЕСЛИ d_a = 1, d_fe = О, S^ * S,, S-Э * S4, БД = О + 0^ И .Да) _ _s3 _{+ s}« _{то в слове v}> имеется байт ошибок є, _, e.g. ^є4р-і' ^є4р ^{Bsca 3}* ^нУ^левой символ є. _і = о в этом байте имеет локатор a_4p-i = s₁ .

4. ЕСЛИ d„ = 0, d_h = 1, S? * S,, Б? * БД, Si = О + 0? И
,vi о а о і j і j j і

^fQ ^{= S}1 ^{+ S}3' ^{T0 B СЛ0ЕЄ v}' ИМееТСЯ баЙТ ОШИбОК 4^..31 ^S4q-2'

є. ₁, є. веса 3. Нулевой символ ^eAa-j ~ ^{Б этш байте} имеет локатор <,„ . = б. .

5. Если d_& = d_fc = О, s₁ = о, s, it о и t^ ' = SI, то в слове

v' имеется байт ошибок е₄р-Э' ^е4р-2' ^е4р-1' ^є4р ^{веса 4}'

6. Есж d_a = d_b = о, s₁ = о, s₃ * о и i^> = s₃, то в слове
v' тлеется байт ошибок е, _э, е. ₂, е. ^, е. веса 4.

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

Лелла 4.1.1. Пусть у= (а_0>а₁,...,а₇,Ъ₀,Ь₁ ,...,Ь₇) - кодовое слово кода HP , 0, сС¹ и $ - локаторы символов aQ'^bO' а⁷"¹ и b^~^s соответственно, і,о = 1,2,...,7. Тогда в слове у = (. а.₀,г₇,Ь_огЪ₇, a^a^.a^j.ag, a₄,a₆,b₂,b₃, b^b^b^.bg ) эквивалентного кода могут быть исправлены наряду с одиночными и двойными независимыми ошибками одиночные байты ошибок длины четыре.

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

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

\ 19 \

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

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

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

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

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

Пусть алгоритм А состоит из последовательности шагов
(подалгоритмов) Л.,-,^ А . Подалгоритм' А_± отображает множес
тво X еходных последовательностей алгоритма А в множество Y_i
выходных последовательностей подалгоритма А^ .

Множество одиночных ошибок F алгоритма А можно представить как F = Р₁ и Р₂ и...и Р₁, где р_± множество одиночных ошибок подалгоритма А^. Выходная последовательность у; = ф_і(х,ї_і), t^Є Fj подалгоритма А^ может не совпадать с выходной последовательностью у_і= ф_і(х,Л.) , получащейся в отсутствии ошибок (Д. обозначает нулевую ошибку).

Подалгоритм А, алгоритма А называется самопроЕерящимся (защищенным от ошибок) для множества входных последовательностей X алгоритма А и множества ошибок Fj подалгоритма А^, если для любых х Є X и Х_±Є Р_і либо уї = y_i , либо у| g Yj.

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

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

\ '.20^1-

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

= Ф₁ v Ф₂ V $_г

Пусть С - комбинационная схема с N входами и м выходами. Схема С однозначно (в отсутствие ошибок) отображает множество х входных последовательностей х =(х₁,х_2>...,х_к), xj= 0,1; і =1.2, ...,N в множество Y выходных последовательностей у = ^.^.-.yjj), У^= 0,1; о -1,2,...,11.

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

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

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

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

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

Пусть у(х,?_и) и у(хД) выходные последовательности схем С(Р_Ц) и С соответственно.

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

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

1. для любого ? , Р с Р_д и любого х є X имеет место у(х,Р_р) = у(х,\) ;

2. существует х' Є X такое, что у(х',Р ) g Y ;

3. для любого х Є X, х * х' либо у(х,Р ) = у(хД), либо yU,P_q) gY .

Подмножество ошибок Р , от которого схема С вполне защищена, будем называть вполне тестируемым. Будем говорить, что ошибка t в У схемы С тестируема с минимальной (максимальной) задержкой X., если т„ минимальное (максимальное) вполне тести-

руемоє подмножество, содержащее f_i , и A._i = q_i - 1 .

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

4. любая ошибка ^Р тестируема с минимальной задержкой А.. И max А,. = А, ;

5. для любой ошибки f. Є ї и любого собственного подмножества

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

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

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

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

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

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

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

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

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

3. Вычислить ь_вцх = Ъ* - е*.

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

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

^ьвых ^{= ь}вых ~ ^ь' ^{!: сч:ітать} выходом алгоритма пару (^ь_Вых^,ъвых^ Тогда у = { у = (Ь_шх,ь^_ых): s(b_BffiC) = О, иь_вых) < t } и алгоритм Ау становится самопроверяющимся.

Для кодов ЕЧХ предлагается более эффективное решение.

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

I М⁽¹⁾(7.}, L'⁽³⁾<:-:) K^(2t-1)(x) }, где !J⁽¹⁾(x) - минимальный

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

Рассматривается алгоритм декодироваїшя <%щ- двоичного кода

22!

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

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

3=0

2+-1
b'stb^.bg ь^), многочлен S(z) = S^Z³' , s. = b'id^).

,2t

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

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

4. Найти локаторы и позиции ненулевых символов слова-ошибки

& = (е^ ,Єр>...,8 ) .

5. Вычислить ь_В1К = ъ'. - е .

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

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

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

a(s) = s + a,jS + ... + . a_t_₁z + a_t, a_t * 0

¹¹ - t t-l

b(z) = z + b.,s + ... + . b_t_₁c + b_t, b_t * 0,

не имеющие кратных корней и полностью разлагающееся в GF(q) на

линейные множители, и вес w(a(z) - b(z)) = 1.

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

Теорема 5.4.1. Алгоритм Л_БЧХ является самоггроверящимся и функция ф,,

ф _ | о, если синдром s(b_EUX) = о, ² і і, в противном случае, является анализатором безошибочности алгоритма Agq%.

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

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

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

23 і.

Лажжа ъ.ь.г. Для нечетного т и любого элемента (3 поля GF(2^m) найдется слово ь* = ъ + в' , где ь - кодовое СЛОВО (n,k)~ кода БЧХ с минимальным расстоянием d = 6 и к > 2^m~¹ , е' -слово-ошибка веса w(e') < г , такое ,что р = s., , и слоео ь"

= Ь + в" , w(e") < г , ДЛЯ КОТОРОГО @ = s₃ .

Лелжх 5-5-3. Для любых Pj, Є GP(2^m) найдется слово ь* = ь + е', w(e') = 2 такое, что ( S₁ + f^ )³ + s, + p? = I .

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

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

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

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

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

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

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

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

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

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

V ' 2^ \

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

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

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

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

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

Пусть z₁ - линейный (1б,14)-код Рида-Соломона над GF(2⁴) с минимальным расстоянием <ц = 3, Z₂ - двоичный нелинейный (16,8)-код Нордстрома-Робкнсона с минимальным расстоянием сц = б.

Обозначим через V₁ [xj Z₁ - двоичный каскадный код, являющийся произведением внутреннего двоичного (5,4)- кода v₁ с проверкой на четность и внешнего (1б,14)-кода Рида-Соломона над GP(2⁴) . Пусть v = v₁ ф v₂ - линейное 5-мэрное пространство и

^V2 ^{в Z}2 ~ ^итеР^{атиЕНЫЙ} ДВОИЧНЫЙ КОД.

Множество слов, являющихся всевозможными суммами слов КОДОВ X = v₁ [х] z₁ и Y = Y₂ z₂, образует нелинейный составной код V. Параметры кода V : длина п = 80, число информационных символов к = 64, минимальное расстояние d = 6. Код V образует обобщенный каскадный код второго порядка и это используется в алгоритме кодирования.

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

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

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

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

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