Устройство декодирования для коррекции тройных ошибок

 

Изобретение относится к области вычислительной техники, а именно к устройствам контроля запоминающих устройств, и может быть использовано для повышения надежности запоминающих устройств. Устройство декодирования для коррекции тройных ошибок содержит блок вычисления синдрома, блок сумматоров по модулю два, три элемента ИЛИ, шесть блоков постоянной памяти, шесть сумматоров по модулю n, блок элементов ИЛИ, два блока умножения на три, коммутатор. 5 ил., 1 табл.

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

Известны устройства декодирования кодов Боуза-Чоудхури-Хоквингейма (БЧХ), содержащие блок вычисления синдрома, схему анализа ошибок, дешифратор коррекции ошибок и корректирующие сумматоры по модулю два, позволяющие производить коррекцию двойных ошибок с высоким быстродействием. Однако данное устройство не позволяет корректировать тройные ошибки /1, 2/.

Наиболее близким по технической сложности к схемному решению к изобретению является устройство декодирования для коррекции двойных ошибок, содержащее блок вычисления синдрома, входы которого соединены с контрольными и информационными входами устройства и первыми входами блока сумматоров по модулю два, первые, вторые и третьи выходы блока вычисления синдрома соединены соответственно с входами первого, второго и третьего постоянных запоминающих устройств (ПЗУ), выходы первого ПЗУ соединены с первыми входами первого, второго, третьего и четвертого сумматоров по модулю n, вторыми входами соединенных соответственно с выходами четвертого, пятого, шестого и второго ПЗУ, выходы первого, второго и третьего сумматоров по модулю n соединены соответственно со входами первого, второго и третьего дешифраторов, выходы которых соединены со входами блока элементов ИЛИ, выходы блока элементов ИЛИ соединены со вторыми входами блока сумматоров по модулю два, выходы которых являются выходами устройства /3/.

Однако это устройство не позволяет исправлять тройные ошибки.

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

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

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

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

Известны устройства, позволяющие декодировать коды с кодовым расстоянием d≥7 в другой совокупности признаков,имеющие аппаратурные затраты при низком быстродействии. Это означает, что предложение отвечает критерию "существенные отличия".

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

Таким образом, предложенное устройство создает положительный эффект.

На фиг. 1 представлена блок-схема устройства, на фиг. 2, 3, 4 одна из возможных схем реализации коммутатора, сумматора по модулю n, блока умножения на три, на фиг. 5 проверочная матрица кода (32, 16), исправляющего тройные ошибки, где α- примитивный элемент поля Галуа. В таблице 1 приведены значения ошибочных разрядов, соответствующих им степеней элементов поля синдромов и значения сигналов на выходах коммутатора в соответствии со значениями N₁, N₂ и N₃ на выходах четвертого, пятого и шестого сумматоров по модулю n. Реализация блока вычисления синдрома, дешифраторов, ПЗУ известны. В этих блоках используются элементы И, ИЛИ, НЕ, сумматоры по модулю два, элементы памяти.

Устройство декодирования для коррекции тройных ошибок (фиг.1) содержит блок вычисления синдрома 1, входы 2 которого соединены с контрольными и информационными входами устройства и первыми входами блока 3 корректирующих сумматоров по модулю два, первые 4, вторые 5 и третьи 6 выходы блока вычисления синдрома соединены соответственно с входами первого 7, второго 8 и третьего 9 элементов ИЛИ, а также входами соответственно первого 10, второго 11 и третьего 12 блока постоянной памяти, четвертый 13 выход блока вычисления синдрома соединен с седьмым входом коммутатора 14, выходы 15 первого блока постоянной памяти соединены с входами первого блока умножения на три 16, первыми входами первого 17, второго 18, третьего 19 и четвертого 20 сумматоров по модулю n, выходы 21 второго блока постоянной памяти соединен с входами второго блока умножения на три 22 и вторыми входами четвертого сумматора по модулю n, выходы 23 третьего блока постоянной памяти соединены со вторыми входами пятого 24 и шестого 25 сумматоров по модулю n, первыми входами соединенных соответственно с выходами 25 и 27 первого и второго блока умножения на три, первый 28, второй 29, третий 30, четвертые 31, пятые 32 и шестые 33 входы коммутатора 14 соединены соответственно с выходами первого, второго, третьего элементов ИЛИ, четвертого, пятого и шестого сумматоров по модулю n, первые 34 и вторые 35 выходы коммутатора соединены с первыми и вторыми входами четвертого 36, пятого 37 и шестого 38 блоков постоянной памяти, выходы 39, 40, 41 которых соединены соответственно со вторыми входами первого, второго и третьего сумматоров по модулю n, выходы 42, 43, 44 первого, второго и третьего сумматоров по модулю n соединены соответственно со входами первого 45, второго 46 и третьего 47 дешифраторов, выходы 48, 49, 50 которых соединены с входами блока элементов ИЛИ 51, выходы 52 блока элементов ИЛИ соединены со вторыми входами блока сумматоров по модулю два, выходы 53 которых являются выходами устройства.

В предложенном устройстве используется проверочная матрица Н кода для коррекции тройных ошибок, полученного из БЧХ кода, путем умножения каждого столбца на элемент ((α^-4i) ) (что не меняет корректирующих свойств кода /4/) с добавлением дополнительного разряда проверки на четность. В качестве примера конкретного исполнения представлена проверочная матрица кода длины n+1 32 S = (S₀,S₁,S₂,S₃) = (S₀,α^p,α^q,α^e), где S₀,α^p,α^q,α^l соответственно разряд проверки на четность, верхние, средние и нижние значения разрядов синдрома (см. фиг. 5). Все сочетания тройных ошибок можно разбить на Z [(n-1)(n-2)]/3 C^з₃₁/31 145 классов. Причем каждый класс тройных ошибок (S₀ 1) определяется соответствующими значениями N₁ P_т + q_т, N₂ l_т + 3P_т, N₃ l_т + (-3q_т), постоянными при любом циклическом сдвиге вектора ошибок. Зная N₁, N₂, N₃, а следовательно, класс ошибок и его образующий Е₀ (l₀, l₁, l₂) (то есть номера начальных значений вектора ошибок, при которых сдвиг вектора ошибок равен нулю, причем (l₀ 0), а также p₀, q₀, l₀, по сдвигу (р_т - p₀) определяется фактический вектор ошибок Е_т. Для некоторых сочетаний тройных ошибок элементы , или равны нулю (0). Тогда, если 0, то вычисляется N₁ P_т + q_т и N₂ принимается равным нулю; если , то N₂ l_т + 3p_т и N₁ 0; если то N₃ l_т + (- 3q_т) и nN₁ 0 Для двойных ошибок (S₀ 0) вычисляется N₃=l_т + (-3q_т), а N₂ принимается равным нулю, для одиночных ошибок (S₀ 1) N₁= р_т + q_т 0, N₂ l_т + 3р_т О. Таким образом, множества значений N₁ и N₂ (или N₃ если ) для каждого класса тройных и одиночных ошибок (S₀= 1) не пересекаются со множеством значений N₃ и N₂ 0 для каждого класса двойных ошибок (S₀ 0) (см. таблицу). В таблице второй и третий столбцы указывают на ошибочные разряды и соответствующие им степени элементов поля синдромов (S₁= α^p, S₂= α^q, S₃= α^l). Например, если ошибки произошли в первом, втором и третьем разрядах, то им соответствует синдром S = (1,α¹²,α⁸,α⁹).). В таблице приводится первая строка в классах, которая определяет начальное местоположение вектора ошибок E₀ (l₀,l₁, l₂). Например, ошибкам в первом, втором и третьем разрядах (Е (1,2,3)) соответствует E₀ (0, 1, 2) и p₀ 11, q₀= 9, l₀= 12.

Устройство работает следующим образом. Кодовые слова поступают на входы 2 блока вычисления синдрома 1. На выходах 4, 5 и 6 блока 1 формируются значения синдрома , которые поступают на входы первого 10, второго 11 и третьего 12 ПЗУ, на выходах которых выделяются р_т, q_т и l_т степени элементов поля синдромов в двоичном коде. На выходах четвертого 20, пятого 24 и шестого 25 сумматоров по модулю выделяются соответственно суммы (р_т + q_т), (l_т+ 3р_т) и (l_т + (-3q_т)) (умножение р_т и q_т на (±3) осуществляется соответственно в блоках 16 и 22), которые поступают соответственно на четвертые 31, пятые 32 и шестые 33 входы коммутатора 14. На первый 28, второй 29 и третий 30 входы коммутатора 14 поступают сигналы с выходов соответственно первого 7, второго 8 и третьего 9 элементов ИЛИ. На седьмой вход коммутатора 14 поступает сигнал контроля на четность с четвертого 13 выхода блока вычисления синдрома, который равен единице для ошибок кратности один и три и равен нулю для двойных ошибок.

При то есть неравных нулю синдромах на выходах 34, 35 коммутатора соответственно устанавливаются значения N₁= p_т + q_т, N₂ l_т + 3р_т. Если одно из значений или равно нулю, то на выходе соответствующего элемента ИЛИ 7, 8 или 9 устанавливается нулевой сигнал. Тогда при на первых 34 выходах коммутатора 14 устанавливается в двоичном коде значение N₁= р_т + q_т, а на вторых 35 выходах коммутатора 14 нули; при на выходах 34 нулевые сигналы, а на выходах 35 соответственно N₂ l_т + 3 р_т или N₃ l_т + (- 3q_т ). При одиночной ошибке на выходах 34, 35 коммутатора нули (см. фиг. 5). Если произошла двойная ошибка (S₀ 0), то на первых 34 выходах коммутатора устанавливается значение N₃ l_т + (-3q_т), а на вторых 35 выходах коммутатора нули. Сигналы с выходов коммутатора 14 поступают на входы четвертого 36, пятого 37 и шестого 38 блоков постоянной памяти. На выходах 39, 40, 41 этих блоков постоянной памяти в двоичном коде устанавливаются значения р₀, р' р₀ l₁, р_'' р₀ l₂ согласно сигналам на выходах коммутатора. Сигналы о значениях р⁰, p' и р" поступают на входы сумматоров 17, 18, 19. На выходах первого 17, второго 18 и третьего 19 сумматоров по модулю n устанавливаются соответственно значения (р_т - p₀), (р_т р' ) и (р_т р"), то есть номера трех ошибочных разрядов в двоичном коде. Например, если на выходе соответственно первого 10, второго 11 и третьего 12 блоков постоянной памяти р_т 12, q_т 8, l_т= 9, то на четвертых 31, пятых 32 и шестых 33 входах коммутатора 34 соответственно N₁ р_т + q_т 20, N₂ l_т + 3р_т 14, N₃ l_т + (-3q_т ) 16 в двоичном коде (на первом 28, втором 29, третьем 30 и седьмом 13 входах коммутатора 14 - единичные сигналы). В этом случае на первых 34 и вторых 35 выходах коммутатора 14, соединенных со входами четвертого 36, пятого 37 и шестого 38 блоков постоянной памяти, устанавливаются в двоичном коде значения N₁ 20 и N₂ 4. Для этих значений начальное местоположение вектора ошибок E₀ (0, 1, 2) и на выходах 39, 40, 41 блоков постоянного памяти 36, 37, 38 устанавливается соответственно р₀ 11, р' p₀ l₁ 10, р" p₀ l₂ 9. Тогда на выходах 43, 44, 45 сумматоров 17, 18, 19 соответственно р_т p₀ 12 11 1, р_т р' 12 - 10 2, р_т р" 12 9 3, то есть Е_т (1,2,3). Ошибки произошли в первом, втором и третьем разрядах кодового слова. Сигналы, указывающие на местоположение ошибочных разрядов с выходов 42, 43, 44 сумматоров 17, 18, 19 поступают на входы дешифраторов 45, 46, 47. На одном из выходов 48, 49, 50 каждого из дешифраторов 45, 46, 47 появляется единичный сигнал, указывающий на соответствующий номер ошибочного разряда. В блоке элементов ИЛИ 51 эти сигналы объединяются, в результате на выходах 52 блока 51 формируется суммарный вектор ошибок, который и корректирует в блоке 3 считываемую информацию. Если произошла одиночная сшибка, например, во втором разряде, то на выходах 4, 5, 6 блока вычисления синдрома соответственно 31 ≡ 0, в двоичном коде; на первом 28, втором 29, третьем 30 и седьмом 13 входах коммутатора единичные сигналы, на четвертых 31, пятых 32 и шестых 33 входах соответственно N₁ (2 + 29) mod 31 ≡ 0, N₂= (25 + 3·2) mod 31 ≡ 0 N₃ (25 + (-3·29)) mod 31 ≡ 2; На выходах 34, 35 коммутатора, соединенных со входами четвертого 36, пятого 37 и шестого 38 блоков постоянной памяти устанавливаются в двоичном коде N₁ 0 и N₂ 0. На выходах 39, 40, 41 четвертого, пzтого и шестого блоков постоянной памяти устанавливается нуль в двоичном коде (p₀ 0, l₀ l₁ l₂=0), который поступает на вторые входы первого, второго и третьего сумматоров по модулю n, на первые входы которых поступает р_т 2. Тогда на выходах 42, 43, 44 первого, второго и третьего сумматоров число два в двоичном коде, на соответствующих выходах первого, второго и третьего дешифраторов единичные сигналы, которые объединяются в блоке элементов ИЛИ 51, и на выходы блока 51 поступает вектор ошибок (Е_т (2)).

При двойной ошибке S₀ 0 на четвертом 13 выходе блока вычисления синдрома нулевой сигнал. Пусть при этом р_т 20, q_т 15, l_т 20 (сигналы соответственно на выходах первого 10, второго 11 и третьего 20 блоков постоянной памяти. В этом случае на первых 34 выходах коммутатора 14 N₃ l_т + (-3q_т) (20 + (-3·15)) mod 31 6; на вторых 35 выходах коммутатора нулевой сигнал. Этим сигналам соответствует начальное местоположение вектора ошибок E₀ (0,1) и на выходах четвертого 36, пятого 37 и шестого 38 блоков постоянной памяти устанавливаются значения p₀ 18, р' 17, р" 17; следовательно, на выходах первого 17, второго 18 и третьего 19 сумматоров по модулю n (р_т р₀) (20 18) mod 31 ≡ 3; (р_т р') (20 17) mod mod31 ≡ 3. (р_т р") (20 17) mod α²,α²⁹,α²⁵ Таким образом, Е_т (2,3).

На соответствующих выходах дешифраторов устанавливаются единичные сигналы, которые объединяются в блоке элементов ИЛИ 51, на выходах 52 блока 51 формируется суммарный вектор ошибок, который и корректирует в блоке 3 считываемую информацию. ТТТ1 ТТТ2 ТТТ3 ТТТ4 ТТТ5

Формула изобретения

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10