ДЕКОДЕР С ИСПРАВЛЕНИЕМ ОШИБОК Российский патент 1996 года по МПК H03M13/00 

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

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

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

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

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

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

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

На фиг. 1 представлена функциональная схема декодера с исправлением ошибок; на фиг. 2 примеры выполнения традиционным способом для поля CF(2⁴) соответственно формирователя синхрома и генератора локаторов; на фиг.3,5 соответственно примеры выполнения блока выбора режима и вычислителя поправок, а также входящего в его состав арифметико-логического узла; на фиг.6 сигналы синхронизации работы декодера; на фиг.7 9 три варианта сигналов, управляющих работой регистров в вычислителе поправок.

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

Сначала вычисляются элементы S_j (j 0,1,2,3) синдрома
S_j= U_iZj+1i

(1) где n длина (число разрядов) кодового слова, подлежащего декодированию;
U_i и Z_i -соответственно символы и локаторы позиций кодового слова.

Если все элементы S_j равны нулю, то ошибок в принятом кодовом слове нет, и информационные символы кодового слова выдаются потребителю. Если в кодовом слове искажен один символ, то должно выполняться условие
(2) причем ни один элемент S_j синдрома не равен нулю. В этом случае локатор Z_γ ошибки и ее значение Е₁ находят из выражений
Z_γ= E₁= (3)
При наличии в кодовом слове двух ошибок условие (2) не выполняется. Тогда вычисляются корни следующего многочлена локаторов ошибки
Λ (X) X² + Λ₁ X + Λ_о, (4)
Коэффициенты этого многочлена определяются системой уравнений
(5)
Решая систему (5) и вводя подстановку X Λ₁ · y, преобразуем уравнение (4) к виду
y² + y + C 0, (6) где
C (7)
A S21

+ A_o S₂;
B S₁ S₃ + S22 (8)
Решив полученное квадратное уравнение (6) по известной методике (Э.М. Габидулин и В.Б.Афанасьев. Кодирование в радиоэлектронике. М. Радио и связь, 1986, с. 58-64), получаем его корни y₁ и y₂. Поскольку по теореме Виета y₁ + y₂ -1, а также с учетом подстановки Х Λ₁ y, локаторы ошибок определяются из соотношений Z_j1= Z_y2= Подставив Λ₁ выраженную через элементы синдрома в системе уравнений (5), имеем
Z_j1= •
Z_j2= • (9)
Значения ошибок находятся из следующей системы уравнений
(10)
После соответствующих преобразований и подстановок, получим
E₁= y21(y₁+1)(S_oZ_j2+S₁)
E₂= y₁(y₁+1)(S_oZ_j1+S₁) (11)
В случае, когда S₁ 0, свободный член С уравнения (6) вычисляется по формуле
C (12)
При этом выражения (9) и (11) примут вид:
Z_j1= Z_j2= (13)
E₁= y21S2o E₂= (y₁+1)²• S2o (14)
По найденным локаторам и значениям ошибок осуществляют их исправление.

Случаи, когда S_o S₁ 0, или S_o S₂0, или S₁ S₃ 0, или S₁ S₂ 0 при неравенстве нулю остальных двух элементов синдрома, а также случай, когда уравнение (6) не имеет решений, соответствуют случаям отказа от декодирования.

Декодер с исправлением ошибок по выше приведенному алгоритму содержит блок 1 буферной памяти, формирователь 2 синдромов, вычислитель 3 поправок, блок 4 выбора режима, генератор 5 локаторов первый и второй блоки 6, 7 суммирования, первый и второй блоки 8, 9 равнозначности, элемент ИЛИ 10 и синхронизатор 11. Информационные входы блока 1 и формирователя 2 объединены и являются информационными входами 12 декодера, информационный вход синхронизатора 11 является входом 13 синхронизации декодера. Группы выходов формирователя 2, число которых равно числу элементов S_j синдрома, подключены к одноименным группам информационных входов вычислителя 3 и блока 4, первый и второй выходы которого соединены с одноименными управляющими входами вычислителя 3. Выходы блока 1 и первая группа выходов вычислителя 3 подключены к первой и второй группам информационных входов блока 6, выходы которого и вторая группа выходов вычислителя 3 соединены с первой и второй группами информационных входов блока 7, выходы которого являются информационными выходами 14 декодера.

Третья и четвертая группы выходов вычислителя 3 подключены к первым группам входов блоков 8 и 9 соответственно, вторые группы входов которых соединены с выходами генератора 5, а выходы с управляющими входами соответственно блоков 6 и 7. Первый и второй выходы вычислителя 3 подключены соответственно к первому входу элемента ИЛИ 10 и управляющему входу блока 4, третий выход которого соединен с управляющим входом синхронизатора 11, первый четвертый выходы которого подключены к входам синхронизации соответственно блока 1, формирователя 2, вычислителя 3 и генератора 5. Четвертый выход блока 4 соединен с вторым входом элемента ИЛИ 10, выход которого является выходом 15 отказа от декодирования декодера.

Блок 1 буферной памяти в рассматриваемом случае представляет собой четыре параллельно соединенных n-разрядных регистра сдвига для промежуточного хранения кодового слова, каждый символ U_i (()) которого является элементом поля GF (2⁴).

Формирователь 2 синдромов может быть выполнен (фиг.2) на четырех регистрах 16-19, четырех умножителях 20-23 на постоянное значение и четырех сумматорах 24-27, первые группы входов которых соответственно объединены и являются входами формирователя. Выходы сумматоров 24-27 подключены к информационным входам соответствующих регистров 16-19, входы синхронизации которых объединены и являются входом синхронизации формирователя 2. Выходы регистров 16-19 через соответствующие умножители 20-23 подключены к вторым группам входов соответствующих сумматоров 24-27 и одновременно являются соответствующими группами выходов формирователя 2. В умножителях 20-23 выходные сигналы регистров 16-19 умножаются на соответствующие локаторы Z_o-Z₃ позиций, после чего суммируются в сумматорах 24-27 с очередными символами. На выходах регистров 16-19 формируются элементы S_o-S₃ синдрома согласно выражению (1).

Блок 4 выбора режима может быть реализован (фиг.3) на элементах 28-32 ИЛИ-НЕ, элементах И 33-38 и элементе ИЛИ 39. Входы первого-четвертого элементов ИЛИ-НЕ 28-31 являются соответственно первой четвертой группами входов блока 4, на которые с формирователя 2 поступают соответствующие элементы S_o-S₃ синдрома. Выход первого элемента ИЛИ-НЕ 28 соединен с входами первого-третьего элементов И 33-35, выход второго элемента ИЛИ-НЕ 29 с входами первого, второго, четвертого и пятого элементов И 33,34,36,37, выход третьего элемента ИЛИ-НЕ 30 с входами первого, третьего и четвертого элементов И 33,35,36, а выход четвертого элемента ИЛИ-НЕ 31 со входами первого и пятого элементов И 33,37. Кроме того, выходы элементов ИЛИ-НЕ 28-31 подключены 5 к входам пятого элемента ИЛИ-НЕ 32, выход которого соединен с одним входом шестого элемента И 38, другой вход которого является управляющим входом блока 4, а выход 40 первым выходом блока 4. Выход 41 второго элемента ИЛИ-НЕ 29 является вторым выходом блока 4, выход 42 первого элемента И 33 третьим выходом блока 4. Выходы второго пятого элементов И 34-37 подключены к входам элементов ИЛИ 39, выход которого 43 является четвертым выходом блока 4.

Генератор 5 локаторов формирует на своих выходах локаторы Z_o-Z_n-1-позиций и может быть выполнен (фиг.4) на триггерах 44-47 и элементе ИСКЛЮЧАЮЩЕЕ ИЛИ 48, выход которого соединен с D-входом первого триггера 44, выход которого подключен к входу элемента 48 и является первым выходом генератора 5. Выход второго триггера 45 соединен с другим входом элемента 48 и является вторым выходом генератора 5. Выходы третьего и четвертого триггеров 46, 47 подключены к D-входам триггеров 45 и 46 соответственно и являются третьим и четвертым выходами генератора 5. D-вход четвертого триггера 47 соединен с выходом первого триггера 44. С-входы триггеров 44-47 объединены и являются входом синхронизации генератора 5, а объединенные R-входы триггеров 44, 47 и S-входы триггеров 45, 46 входом обнуления генератора 5. Такая реализация генератора 6 соответствует порождающему многочлену m(x) X₄+ X + 1 в поле GF (24).

Вычислитель 3 поправок реализуется для данного случая (фиг.5) на арифметико-логическом узле 49, первом и втором блоках 50, 51 переключений, первом четвертом регистрах 52-55 и блоке 56 управления и синхронизации. Первая четвертая группы 57 информационных входов блока 50 являются соответствующими группами информационных входов вычислителя 3. Группы выходов блока 50 соединены с соответствующими группами информационных входов узла 49, четыре группы выходов которого подключены к соответствующим группам информационных входов блока 51. Группы выходов блока 51 соединены с информационными входами соответствующих регистров 52-55, выходы которых подключены к пятой восьмой группам информационных входов блока 50. Первый и второй входы 58, 59 блока 56 являются одноименными управляющими входами вычислителя 3. Первая группа выходов блока 56 соединена с соответствующими управляющими входами узла 49, выход 60 которого является первым выходом вычислителя 3. Выходы 61-64 соответственно третьего, четвертого, первого и второго регистров 54, 55, 52, 53 являются соответственно первой четвертой группами выходов вычислителя 3, а второй выход 65 узла 49 вторым выходом вычислителя 3. Вторая и третья группы выходов блока 56 соединены с управляющими входами блоков 50, 51, первый четвертый выходы блока 56 подключены ко входам синхронизации регистров 52-55.

Арифметико-логический узел 49 включает в себя (фиг.5) первый четвертый перемножители 66-69, первый третий сумматоры 70-72, первый третий блоки 73-75 возведения в квадрат, блок 76 возведения в четвертую степень, первый пятый переключатели 77-81, блок 82 равнозначности и блок 83 умножения на матрицу. Управляющие входы блоков 74, 75, 73, сумматоров 70, 71, 72, блока 83 и переключателей 77-81 являются соответствующими управляющими входами узла 49. Информационные входы блока 73, первая и вторая группы входов перемножителя 66, информационные входы блока 74, первые группы информационных входов переключателей 77, 78 и вторые группы информационных входов переключателей 80, 81 являются соответственно первой восьмой группами информационных входов узла 49. Выходы блока 73 и перемножителя 66 соединены с группами информационных входов сумматора 70, выходы которого подключены первым группам входов перемножителя 69 и блока 82 и являются первой группой выходов узла 49. Выходы блока 83 и сумматора 72 являются второй и третьей группами выходов узла 49. Выходы блока 74 подключены к второй группе информационных входов переключателя 77 и информационным входам блока 75, выходы которого соединены со второй группой информационных входов переключателя 78, первой группой информационных входов переключателя 80 и одной из групп информационных входов сумматора 71. Выходы переключателей 77 и 78 подключены к группам входом перемножителя 67, выходы которого соединены с входами блока 76 и другой группой информационных входом сумматора 71. Выходы блока 76 подключены к первой группе информационных входов переключателя 79, выходы сумматора 71 соединены с второй группой информационных входов переключателей 79, второй группой входов блока 82 и является четвертой группой выходов узла 49. Выходы переключателей 79, 80 подключены к группам входов перемножителя 68, выходы которого соединены с первыми группами информационных входов сумматора 72 и переключателя 81, выходы которого подключены ко второй группе входов перемножителя 69, выходы которого соединены со второй группой информационных входов сумматора 72 и информационными входами блока 83. Старший разряд выходов перемножителя 69 является первым выходом узла 49, а выход блока 82 вторым выходом узла 49.

Переключатели 77-81 могут быть реализованы в микроэлектронном исполнении в виде полупроводниковых ключей.

Все перемножители 66-69 и умножители 20-23 и 83 и все блоки 73-76 возведения в степень осуществляют все операции в поле GF(2⁴) и могут быть выполнены в виде известных комбинационных схем. Сумматоры 24-27 являются сумматорами по модулю 2, а блоки 6.7 суммирования и сумматоры 70-72 являются сумматорами по модулю 2 с управляемыми вентилями по входу b. Логика работы этих блоков в зависимости от сигналов управления показана в табл.1. Блоки возведения в квадрат 73-75 содержат мультиплексоры, которые работают в зависимости от сигналов управления согласно табл.2, где комбинация v=11 не используется.

Блок 83 умножения на матрицу, который работает согласно табл.3, осуществляет умножение входного кода на матрицу, позволяющую найти корни уравнения (6) y₁ и y₂, и зависит от порождающего многочлена m(x) (см.выше упомянутую книгу Э.М.Габидулина и В.Б.Афанасьева).

Синхронизатор 11 работает в соответствии с диаграммой на фиг.6.

Блок 56 управления и синхронизации может быть выполнен известными схемотехническими способами, обеспечивающими его работу согласно табл.4. В этой таблице знаком "х" отмечены произвольные состояния соответствующих сигналов, а "Н" и "В" обозначают соответственно нижнее и верхнее положения переключателей 77-81 на фиг.5. Числа в таблице соответствуют нумерации элементов на фиг.5. Комбинация одновременного появления сигналов ОNE=1 и SEC=1 не используется. Сигналы синхронизации на регистры 52-55 формируются в блоке 56 согласно диаграммам фиг.7.

Декодер с исправлением ошибок работает следующим образом.

На вход 13 поступает либо тактовый сигнал с опорной частотой F, либо сигнал словной (блочной) синхронизации для привязки фазы генератора частоты F в сихронизаторе 11. По сигналу с частотой F в синхронизаторе 11 вырабатываются сигналы F1-F4 (фиг.6).

По сигналу F1 в первых n тактах в блок 1 записывается очередное кодовое слово. Одновременно с этим по сигналу F2 то же кодовое слово подается в формирователь 2, на выходах которого в n-ном такте формируются элементы S_o S₃ cиндрома согласно (1). Эти элементы поступают на блок 4 выбора режима, в котором в зависимости от соотношений между элементами S_о-S₃ формируются соответствующие сигналы.

Если все элементы S_о-S₃ синдрома равны нулю, это означает отсутствие ошибки в принятом слове. На выходе 42 блока 4 в этом случае вырабатывается единичный сигнал END, разрешающий выдачу принятого кодового слова потребителю без исправлений. Синхронизатор 11 по этому сигналу сразу начинает формировать вторую половину сигнала F1, по которому коды с блока 1 проходят на выходы 14. Поскольку вычислитель 3 в этом режиме никаких сигналов не выдает, а блоки 6.7 управляющие сигналы не поступают. Поэтому блоки 6 и 7 пропускают выходные сигналы блока 1 без изменений.

Если в принятом кодовом слове искажены более двух символов, появляется сигнал ERR на выходе 43 блока 4. Этот сигнал проходит на выход 15, индицируя невозможность исправления данного кодового слова. По сигналу ERR во внешней схеме может быть осуществлен запрет передачи данного слова потребителю либо организован переспрос передатчика. В частном случае данный сигнал ERR может быть введен в синхронизатор 11, который в этом случае выдаст сигнал обнуления блока 1 и сразу перейдет к новому циклу формирования сигналов F1-F4.

Отсутствие сигналов END и ERR на выходах 42 и 43 блока 4 означает наличие одной или двух ошибок в принятом кодовом слове. В этом случае вычислитель 3 по сигналу F3 с синхронизатора 11 осуществляет вычисление локаторов Z, Z_γ2 и значений Е₁, Е₂ ошибок. При этом в нулевом состоянии (см.табл.4) узел 49 определяет истинность выражения S_оС₂ S21

и S₁S₃ S22 (15). Если блок 82 равнозначности индицирует равенство, т.е. с выхода 60 вычислителя 3 на блок 4 поступает единичный сигнал ЕQ, а блок 4 в это же время определяет, что для любого j имеет место S_j ≠ 0, то с выхода 40 блока 4 на вход 58 вычислителя 3 поступает единичный сигнал ONE, свидетельствующий о наличии только одной ошибки в принятом кодовом слове. При этом работа вычислителя 3 производится в соответствии с первым вариантом табл.4 и фиг.8а.

На выходах 63 регистра 52 в первом состоянии этого варианта декодирования и а выходах 61 регистра 54 во втором состоянии формируются соответственно локатор Z_γ1 1 и значение Е₁ ошибки согласно (3). Когда синхронизатор 11 начинает выдавать сигнал F4 (и вторую половину сигнала F₁), генератор 5 начинает потактовое формирование локаторов Z_i позиций в кодовом слове, которое при этом потактово выводится из блока 1. Локаторы Z_i соответствуют позиции символа кодового слова, выводимого в данный момент из блока 1. При равенстве очередного локатора Z_i, сформированного генератором 5, с локатором Z_γ1 ошибки на выходах 63 вычислителя блок 8 выдает управляющий сигнал на блок 6, по которому в блоке 6 искаженный символ, выводимый в этом такте из блока 1, суммитируется по модулю два со значением Е₁ ошибки с выходов 61 вычислителя 3. В результате исправленный символ поступает на выходы 14 декодера. В остальные такты блок 6 пропускает символы без изменения. Блоки 7 и 9 в этом варианте декодирования не используются, т.к. на выходах 64 вычислителя отсутствует код локатора Z_γ2 (нет второй ошибки) и управляющий сигнал на блок 7 с блока 9 не выдается.

Если в нулевом состоянии (таблица) блок 82 не выдает сигнал ЕQ, это означает (при нулевых сигналах END и ERR с выходов 42, 43 блока 4) наличие двух ошибок в принятом кодовом слове. В этом случае на выходе 40 блока 4 сигнал ONE отсутствует. Если элемент S₁ синдрома не равен нулю, то отсутствует и сигнал SEC на выходе 41 блока 4. Вычислитель 3 тогда работает по второму варианту табл.4 и фиг.8. определяя локаторы Z_γ1, Z_γ2и значения Е₁, Е₂ ошибок согласно выражениям (7)-(9) и (11). В каждом состоянии (на каждом шаге, в каждой итерации) этого варианта в соответствующие регистры 52-55 записываются комбинации элементов S_j, вычисленные в этом состоянии, причем как запись в эти регистры с группы выходов узла 49, так и считывание из них на соответствующие групп входов узла 49 осуществляются с помощью блоков 50, 51 в соответствии с табл.4 и фиг.8. Поскольку узел 49 является асинхронной комбинационной схемой, длительность каждого состояния определяется лишь задержкой в элементах узла 49 и временем срабатывания блоков 50, 51.

Следует отметить, что как во втором, так и в третьем вариантах декодирования наличие в каком-либо состоянии табл.4 обозначения 54(1) означает, что при считывании из третьего регистра 54 данных через блок 50 в узел 49 вместо младшего разряда этих данных записывается величина, указанная в скобках.

По завершении выдачи синхронизатором 11 сигнала F3 на выходах 63 и 64 вычислителя 3 устанавливаются значения локаторов Z_γ1,Z_γ2 обеих ошибок, а на выходах 61 и 62 вычислителя 3 значения Е₁, Е₂ этих ошибок. Далее по сигналу F4 с синхронизатора 11 генератор 5 начинает формировать локаторы Z_i позиций, а кодовое слово по сигналу F1 поступает из блока 1. Аналогично первому варианту (при одной ошибке) в момент равенства локатора Z_i с одним из локаторов Z ₁ или Z ₂ соответствующий блок 8 или 9 выдает управляющий сигнал на соответствующий блок 6 или 7, где производится суммирование по модулю два искаженного символа и значения Е₁ или Е₂ ошибки. Исправленное кодовое слово поступает на выход 14.

В том случае, когда на выходе 41 блока 4 присутствует единичный сигнал SEC, свидетельствующий о равенстве нулю элемента S₁, вычисление свободного члена С в уравнении (6) по выражению (7) некорректно. Поэтому вычисления в соответствии с выражениями (12)-(14) для этого режима производится согласно третьему варианту табл.4 и фиг.9. В остальном работа декодера происходит так же, как и во втором варианте.

Если во втором или третьем вариантах декодирования в третьем состоянии (табл. 4) в старшем разряде выходов перемножителя 69 узла 49, т.е. на выходе 65 вычислителя 3 формируется единичный сигнал ER(3), то он поступает через элемент ИЛИ 10 на выход 15 отказа от декодирования. Это связано с тем, что в данном случае для порождающего многочлена m(x) x₄ + x + 1 не выполняется условие существования решения квадратного уравнения (6).

Обнуление (начальная установка) генератора 5 может осуществляться специальным сигналом в промежутки между выдачами сигналов F4 либо автоматически по снятию сигнала F4.

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

Быстродействие декодера может быть увеличено за счет совмещения операций вывод кодового слова из блока 1 и записи в блок 1 следующего кодового слова. Кроме того, может быть предусмотрено сокращение времени выдачи сигнала F3 при наличии одной ошибки и отказ от выдачи сигналов F3 и F4 в случае отказ от декодирования.

Изобретение относится к вычислительной технике. Его применение в системах связи, использующих коды с исправлением ошибок, позволяет повысить быстродействие и снизить сложность устройства. Декодер содержит блок 1 буферной памяти, формирователь 2 синдромов, вычислитель 3 поправок, блок 4 выбора режимов, генератор 5 локаторов и блок 6 суммирования. Технический результат достигается благодаря введению блока 7 суммирования, блоков 8, 9 равнозначности, элемента ИЛИ 10 и синхронизатора 11. Декодер обеспечивает исправление одной или двух ошибок в кодовом слове либо отказ от декодирования при наличии большего числа ошибок или отсутствии решения для выбранного порождающего многочлена над полем Галуа. 3 з. п. ф-лы, 4 табл., 9 ил.

1. ДЕКОДЕР С ИСПРАВЛЕНИЕМ ОШИБОК, содержащий блок буферной памяти, информационные входы которого объединены с соответствующими информационными входами формирователя синдрома и являются информационными входами декодера, вычислитель поправок, первая группа выходов которого и выходы блока буферной памяти соединены соответственно с первой и второй группами информационных входов первого блока суммирования, блок выбора режима и генератор локаторов, отличающийся тем, что в него введены второй блок суммирования, блоки равнозначности, элемент ИЛИ и синхронизатор, причем группы выходов формирователя синдромов подключены к одноименным группам информационных входов вычислителя поправок и блока выбора режима, первый и второй выходы которого соединены с первым и вторым управляющими входами вычислителя поправок, вторая группа выходов которого и выходы первого блока суммирования подключены соответственно к первой и второй группам информационных входов второго блока суммирования, выходы которого являются информационными выходами декодера, третья и четвертая группы выходов вычислителя поправок соединены с первыми группами входов соответственно первого и второго блоков равнозначности, выходы которых подключены к управляющим входам соответственно первого и второго блоков суммирования, первый и второй выходы вычислителя поправок соединены соответственно с первым входом элемента ИЛИ и управляющим входом блока выбора режима, третий и четвертый выходы которого подключены соответственно к управляющему входу синхронизатора и второму входу элемента ИЛИ, выход которого является выходом отказа от декодирования декодера, при этом информационный вход синхронизатора является входом синхронизации декодера, а с первого по четвертый выходы синхронизатора соединены с входами синхронизации соответственно блока буферной памяти, формирователя синдромов, вычислителя поправок и генератора локаторов, выходы которого подключены к вторым группам входов первого и второго блоков равнозначности. 2. Декодер по п.1, отличающийся тем, что блок выбора режима выполнен на шести элементах И, элементе ИЛИ и пяти элементах ИЛИ - НЕ, входы с первого по четвертый элементов ИЛИ - НЕ являются соответствующими группами информационных входов блока, выход первого элемента ИЛИ - НЕ соединен с первым входом пятого элемента ИЛИ - НЕ и первыми входами с первого по третий элементов И, выход второго элемента ИЛИ - НЕ соединен с вторым входом пятого элемента ИЛИ - НЕ, вторыми входами первого и второго элементов И, первыми входами четвертого и пятого элементов И и является вторым выходом блока, выход третьего элемента ИЛИ - НЕ соединен с третьими входами пятого элемента ИЛИ - НЕ и первого элемента И и вторыми входами третьего четвертого элементов И, выход четвертого элемента ИЛИ - НЕ соединен с четвертыми входами первого элемента И и пятого элемента ИЛИ - НЕ и вторым входом пятого элемента И, выход которого и выходы с второго по четвертый элементов И соединены с входами элемента ИЛИ, выход которого является четвертым выходом блока, первым выходом которого является выход шестого элемента И, первый вход которого соединен с выходом пятого элемента ИЛИ - НЕ, а второй вход является управляющим входом блока, третьим выходом которого является выход первого элемента И. 3. Декодер по п.1, отличающийся тем, что вычислитель поправок содержит арифметико-логический узел, первый и второй блоки переключений, четыре регистра и блок управления и синхронизации, входы с первого по третий которого являются соответственно первым, вторым управляющими входами и входом синхронизации вычислителя, группы информационных входов с первой по четвертую первого блока переключений являются соответствующими группами информационных входов вычислителя, а группы выходов с первой по восьмую соединены с соответствующими группами информационных входов арифметико-логического узла, первый и второй выходы которого являются соответствующими выходами вычислителя, первая группа выходов блока управления и синхронизации соединена с соответствующими управляющими входами арифметико-логического узла, группы выходов которого с первой по четвертую соединены с соответствующими группами информационных входов второго блока переключений, группы выходов которого с первой по четвертую соединены с информационными входами регистров соответственно с первого по четвертый, вторая и третья группы выходов блока управления и синхронизации соединены с управляющими входами соответственно первого и второго блоков переключений, выходы блока управления и синхронизации с первого по четвертый соединены с входами синхронизации соответствующих регистров, выходы которых соединены с группами информационных входов соответственно с пятой по восьмую первого блока переключений и являются соответственно третьей, четвертой, первой и второй группами выходов вычислителя. 4. Декодер по п. 3, отличающийся тем, что арифметико-логический узел выполнен на четырех перемножителях, трех сумматорах, трех блоках возведения в квадрат, блоке возведения в четвертую степень, блоке умножения на матрицу, блоке равнозначности, пяти переключателях, информационные входы первого блока возведения в квадрат, первая и вторая группы входов первого перемножителя, информационные входы которого блока возведения в квадрат и первые группы информационных входов первого и второго переключателей являются соответственно с первой по шестую группами информационных входов узла, выходы первого блока возведения в квадрат и первого перемножителя соединены соответственно с первой и второй группами информационных входов первого сумматора, выходы которого подключены к первым группам входов блока равнозначности и второго перемножителя и являются первой группой выходов узла, выходы второго блока возведения в квадрат соединены с второй группой информационных входов первого переключателя и информационными входами третьего блока возведения в квадрат, выходы первого и второго переключателей соединены с первой и второй группами входов третьего перемножителя, выходы которого соединены с первой группой информационных входов второго сумматора и входами блока возведения в четвертую степень, выходы которого соединены с первой группой информационных входов третьего переключателя, выходы третьего блока возведения в квадрат соединены с второй группой информационных входов второго переключателя, первой группой информационных входов четвертого переключателя и второй группой информационных входов второго сумматора, выходы которого подключены к второй группе информационных входов третьего переключателя, второй группе входов блока равнозначности и являются четвертой группой выходов узла, выходы третьего и четвертого переключателей соединены с первой и второй группами входов четвертого перемножителя, выходы которого соединены с первыми группами информационных входов третьего сумматора и пятого переключателя, выходы которого соединены с второй группой входов второго перемножителя, выходы которого соединены с второй группой информационных входов третьего сумматора и информационными входами блока умножения на матрицу, старший разряд выходов второго перемножителя является первым выходом узла, вторым выходом которого является выход блока равнозначности, а вторые группы информационных входов четвертого и пятого переключателей являются соответственно седьмой и восьмой группами информационных входов узла, управляющими входами которого являются управляющие входы всех блоков возведения в квадрат, блока умножения на матрицу, всех сумматоров и переключателей, а выходы блока умножения на матрицу и третьего сумматора являются соответственно второй и третьей группами выходов узла.