УСТРОЙСТВО ДЕКОДИРОВАНИЯ КОДОВ РИДА-СОЛОМОНА Российский патент 2012 года по МПК H03M13/45 

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

В настоящее время на практике применяются устройства декодирования кодов Рида-Соломона (PC-кодов), реализующие классические алгоритмы декодирования (Питерсона-Горенстейна-Цирлера, Берлекэмпа-Месси, Евклида), позволяющие исправлять не более t ошибочных символов в кодовом слове (t=(d-1)/2, d - минимальное кодовое расстояние).

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

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

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

Алгоритм работы устройства состоит в следующем: используя оценки надежностей символов принятого кодового слова, вычисляется матрица М, которая определяет интерполяционные точки и их кратность; выполняется процедура интерполяции для нахождения полинома Q_M(X,Y); в полиноме Q_M(X,Y) выделяются сомножители вида Y-f(X); из полиномов f(X) реконструируются кодовые слова; наиболее вероятное из них выбирается как результат работы алгоритма.

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

Наиболее близким по технической сущности к заявляемому изобретению является выбранное в качестве прототипа устройство декодирования кодов Рида-Соломона [3], позволяющее исправить одну дополнительную ошибку за границей половины минимального кодового расстояния. Устройство-прототип содержит: буферную память данных, блок вычисления синдромов, процессор Галуа, блок дискретного преобразования Фурье, блок поиска позиций ошибок веса t+1 и блок вычисления значений ошибок.

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

Недостатком прототипа является относительно низкое быстродействие, обусловленное переборным характером поиска неизвестных невязок при исправлении t+1 ошибок. Количество вычислений возможных значений неизвестной невязки равняется n_S=(n-1+t)(n-t)/2, где n - длина кодового слова кода Рида-Соломона.

Быстродействие декодера [3] может быть увеличено за счет усреднения времени декодирования кодовых слов с различным числом ошибок. Однако при этом для обеспечения постоянной пропускной способности необходимо ввести дополнительный буфер для хранения кодовых слов, что одновременно увеличит задержку данных в декодере.

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

Поставленная техническая задача решается тем, что в устройство декодирования кодов Рида-Соломона, содержащее буферную память данных, блок вычисления синдромов, процессор Галуа, блок дискретного преобразования Фурье, блок поиска позиций ошибок, блок вычисления значений ошибок, первый сумматор элементов поля Галуа, причем входы буферной памяти данных и входы блока вычисления синдромов являются входами символов данных устройства декодирования кодов Рида-Соломона, выходы буферной памяти данных соединены с первыми входами первого сумматора элементов поля Галуа, выходы блока вычисления синдромов соединены с первыми входами процессора Галуа, первые выходы процессора Галуа соединены с первыми входами блока дискретного преобразования Фурье, вторые выходы процессора Галуа соединены со вторыми входами блока дискретного преобразования Фурье, третьи выходы процессора Галуа соединены с третьими входами блока дискретного преобразования Фурье, четвертые выходы процессора Галуа соединены с четвертыми входами блока поиска позиций ошибок, пятые выходы процессора Галуа соединены с первыми входами блока вычисления значений ошибок, шестые выходы процессора Галуа соединены со вторыми входами блока вычисления значений ошибок, седьмые выходы процессора Галуа соединены с третьими входами блока вычисления значений ошибок, вторые выходы блока дискретного преобразования Фурье соединены с третьими входами процессора Галуа, третьи выходы блока дискретного преобразования Фурье соединены с четвертыми входами процессора Галуа, четвертые выходы блока дискретного преобразования Фурье соединены с первыми входами блока поиска позиций ошибок, пятый выход блока дискретного преобразования Фурье соединен со вторым входом блока поиска позиций ошибок, шестые выходы блока дискретного преобразования Фурье соединены с третьими входами блока поиска позиций ошибок, первые выходы блока поиска позиций ошибок соединены с пятыми входами процессора Галуа, вторые выходы блока поиска позиций ошибок соединены с шестыми входами процессора Галуа, третьи выходы блока поиска позиций ошибок соединены с седьмыми входами процессора Галуа, четвертые выходы блока поиска позиций ошибок соединены с восьмыми входами процессора Галуа, выходы блока вычисления значений ошибок соединены со вторыми входами первого сумматора элементов поля Галуа, выходы первого сумматора элементов поля Галуа являются выходами данных устройства декодирования кодов Рида-Соломона, введен блок сортировки позиций символов, причем первые входы блока сортировки позиций символов являются входами оценок надежности символов данных устройства декодирования кодов Рида-Соломона, пятые выходы блока поиска позиций ошибок соединены со вторыми входами блока сортировки позиций символов, первые выходы блока дискретного преобразования Фурье соединены с третьими входами блока сортировки позиций символов, первые выходы блока сортировки позиций символов соединены со вторыми входами процессора Галуа, вторые выходы блока сортировки позиций символов соединены с пятыми входами блока поиска позиций ошибок, причем блок сортировки позиций символов содержит первую схему сравнения кодов, первый блок памяти отсортированных позиций, второй блок памяти отсортированных позиций, третий блок памяти отсортированных позиций, четвертый блок памяти отсортированных позиций, пятый блок памяти отсортированных позиций, первый коммутатор, второй коммутатор, третий коммутатор, четвертый коммутатор, пятый коммутатор, шестой коммутатор, седьмой коммутатор, первый счетчик, второй счетчик, третий счетчик, первый дешифратор, второй дешифратор, причем первые входы первой схемы сравнения кодов являются первыми входами блока сортировки позиций символов, вторые входы первой схемы сравнения кодов соединены с шиной константы Thres, выход первой схемы сравнения кодов соединен со вторым входом первого блока памяти отсортированных позиций, со вторым входом второго блока памяти отсортированных позиций, со вторым входом третьего блока памяти отсортированных позиций, со вторым входом четвертого блока памяти отсортированных позиций и со вторым входом пятого блока памяти отсортированных позиций, первые выходы первого счетчика соединены с первыми входами первого блока памяти отсортированных позиций, с первыми входами второго блока памяти отсортированных позиций, с первыми входами третьего блока памяти отсортированных позиций, с первыми входами четвертого блока памяти отсортированных позиций и с первыми входами пятого блока памяти отсортированных позиций, второй выход первого счетчика соединен с входом второго счетчика, выходы второго счетчика соединены со входами первого дешифратора, первый выход первого дешифратора соединен с третьим входом первого блока памяти отсортированных позиций, второй выход первого дешифратора соединен с третьим входом второго блока памяти отсортированных позиций, третий выход первого дешифратора соединен с третьим входом третьего блока памяти отсортированных позиций, четвертый выход первого дешифратора соединен с третьим входом четвертого блока памяти отсортированных позиций, пятый выход первого дешифратора соединен с третьим входом пятого блока памяти отсортированных позиций, выходы первого блока памяти отсортированных позиций соединены со вторыми входами первого коммутатора и четвертыми входами второго коммутатора, выходы второго блока памяти отсортированных позиций соединены с третьими входами первого коммутатора и пятыми входами второго коммутатора, выходы третьего блока памяти отсортированных позиций соединены с четвертыми входами первого коммутатора и первыми входами второго коммутатора, выходы четвертого блока памяти отсортированных позиций соединены с пятыми входами первого коммутатора и вторыми входами второго коммутатора, выходы пятого блока памяти отсортированных позиций соединены с первыми входами первого коммутатора и третьими входами второго коммутатора, выходы третьего счетчика соединены с шестыми входами первого коммутатора, с шестыми входами второго коммутатора и входами второго дешифратора, первый выход второго дешифратора соединен с третьим входом седьмого коммутатора, второй выход второго дешифратора соединен с третьим входом третьего коммутатора, третий выход второго дешифратора соединен с третьим входом четвертого коммутатора, четвертый выход второго дешифратора соединен с третьим входом пятого коммутатора, пятый выход второго дешифратора соединен с третьим входом шестого коммутатора, первые входы третьего, четвертого, пятого, шестого и седьмого коммутаторов являются третьими входами блока сортировки позиций символов, вторые входы третьего, четвертого, пятого, шестого и седьмого коммутаторов являются вторыми входами блока сортировки позиций символов, выходы третьего коммутатора соединены с четвертыми входами первого блока памяти отсортированных позиций, выходы четвертого коммутатора соединены с четвертыми входами второго блока памяти отсортированных позиций, выходы пятого коммутатора соединены с четвертыми входами третьего блока памяти отсортированных позиций, выходы шестого коммутатора соединены с четвертыми входами четвертого блока памяти отсортированных позиций, выходы седьмого коммутатора соединены с четвертыми входами пятого блока памяти отсортированных позиций, выходы первого коммутатора являются вторыми выходами блока сортировки позиций символов, выходы второго коммутатора являются первыми выходами блока сортировки позиций символов, причем блок памяти отсортированных позиций содержит первый блок памяти с произвольным доступом, второй блок памяти с произвольным доступом, первый логический элемент И-НЕ, второй логический элемент И-НЕ, четвертый счетчик, пятый счетчик, восьмой коммутатор, девятый коммутатор, десятый коммутатор, одиннадцатый коммутатор и вычитатель, причем первые входы первого блока памяти с произвольным доступом, первые входы второго блока памяти с произвольным доступом являются первыми входами блока памяти отсортированных позиций, первый вход первого логического элемента И-НЕ, первый вход второго логического элемента И-НЕ, третий вход восьмого коммутатора, третий вход девятого коммутатора являются третьим входом блока памяти отсортированных позиций, второй вход первого логического элемента И-НЕ, второй вход второго логического элемента И-НЕ являются вторым входом блока памяти отсортированных позиций, выход первого логического элемента И-НЕ соединен со вторым входом первого блока памяти с произвольным доступом и входом четвертого счетчика, выходы четвертого счетчика соединены с первыми входами восьмого коммутатора, вторыми входами одиннадцатого коммутатора и первыми входами вычитателя, выходы восьмого коммутатора соединены с третьими входами первого блока памяти с произвольным доступом, выходы первого блока памяти с произвольным доступом соединены с первыми входами десятого коммутатора, выход второго логического элемента И-НЕ соединен со вторым входом второго блока памяти с произвольным доступом и входом пятого счетчика, выходы пятого счетчика соединены с первыми входами девятого коммутатора, выходы девятого коммутатора соединены с третьими входами второго блока памяти с произвольным доступом, выходы второго блока памяти с произвольным доступом соединены со вторыми входами десятого коммутатора, вторые входы вычитателя и вторые входы восьмого коммутатора являются четвертыми входами блока памяти отсортированных позиций, а старший разряд четвертых входов блока памяти отсортированных позиций соединен с третьим входом одиннадцатого коммутатора, первые выходы вычитателя соединены со вторыми входами девятого коммутатора, второй выход вычитателя соединен с третьим входом десятого коммутатора, выходы десятого коммутатора соединены с первыми входами одиннадцатого коммутатора, выходы одиннадцатого коммутатора являются выходами блока памяти отсортированных позиций, причем блок поиска позиций ошибок содержит первый блок вычисления невязок, второй блок вычисления невязок, первый блок подсчета невязок, второй блок подсчета невязок, двенадцатый коммутатор, первый регистр-защелку, блок памяти коэффициентов, первое местное устройство управления, причем первые входы первого местного устройства управления являются четвертыми входами блока поиска позиций ошибок, вторые входы первого местного устройства управления и первые входы блока памяти коэффициентов являются пятыми входами блока поиска позиций ошибок, третьи входы блока поиска позиций ошибок являются младшими разрядами вторых входов блока памяти коэффициентов, первые входы блока поиска позиций ошибок являются средними разрядами вторых входов блока памяти коэффициентов, второй вход блока поиска позиций ошибок является старшим разрядом вторых входов блока памяти коэффициентов, младшие разряды первых выходов блока памяти коэффициентов соединены с первыми входами первого блока вычисления невязок и с первыми входами второго блока вычисления невязок, средние разряды первых выходов блока памяти коэффициентов соединены с третьими входами первого блока вычисления невязок и с третьими входами второго блока вычисления невязок, старший разряд первых выходов блока памяти коэффициентов соединен с пятым входом первого блока вычисления невязок и с пятым входом второго блока вычисления невязок, младшие разряды вторых выходов блока памяти коэффициентов соединены со вторыми входами первого блока вычисления невязок и со вторыми входами второго блока вычисления невязок, средние разряды вторых выходов блока памяти коэффициентов соединены с четвертыми входами первого блока вычисления невязок и с четвертыми входами второго блока вычисления невязок, старший разряд вторых выходов блока памяти коэффициентов соединен с шестым входом первого блока вычисления невязок и с шестым входом второго блока вычисления невязок, первые выходы первого блока вычисления невязок соединены с шестыми входами двенадцатого коммутатора, вторые выходы первого блока вычисления невязок соединены с пятыми входами двенадцатого коммутатора, третий выход первого блока вычисления невязок соединен с четвертым входом первого блока подсчета невязок, четвертые выходы первого блока вычисления невязок соединены с третьими входами первого блока подсчета невязок, пятый выход первого блока вычисления невязок соединен с третьим входом первого местного устройства управления, первый выход первого блока подсчета невязок соединен с пятым входом первого местного устройства управления, вторые выходы первого блока подсчета невязок соединены с четвертыми входами двенадцатого коммутатора, первые выходы второго блока вычисления невязок соединены с первыми входами двенадцатого коммутатора, вторые выходы второго блока вычисления невязок соединены со вторыми входами двенадцатого коммутатора, пятый выход второго блока вычисления невязок соединен с четвертым входом первого местного устройства управления, четвертые выходы второго блока вычисления невязок соединены с третьими входами второго блока подсчета невязок, третий выход второго блока вычисления невязок соединен с четвертым входом второго блока подсчета невязок, вторые выходы второго блока подсчета невязок соединены с третьими входами двенадцатого коммутатора, первый выход второго блока подсчета невязок соединен с шестым входом первого местного устройства управления, третий выход первого местного устройства управления соединен с седьмым входом первого блока вычисления невязок, четвертый выход первого местного устройства управления соединен с восьмым входом первого блока вычисления невязок, пятый выход первого местного устройства управления соединен с девятым входом первого блока вычисления невязок, шестые выходы первого местного устройства управления соединены с четвертыми входами блока памяти коэффициентов, седьмые выходы первого местного устройства управления соединены с третьими входами блока памяти коэффициентов, восьмые выходы первого местного устройства управления соединены со вторыми входами первого блока подсчета невязок, девятый выход первого местного устройства управления соединен с первым входом первого блока подсчета невязок, десятый выход первого местного устройства управления соединен с пятым входом второго блока подсчета невязок, одиннадцатый выход первого местного устройства управления соединен с четвертым входом первого регистра-защелки, двенадцатые выходы первого местного устройства управления соединены с седьмыми входами двенадцатого коммутатора, тринадцатый выход первого местного устройства управления соединен с пятым входом второго блока подсчета невязок, четырнадцатый выход первого местного устройства управления соединен с первым входом второго блока подсчета невязок, пятнадцатые выходы первого местного устройства управления соединены со вторыми входами второго блока подсчета невязок, шестнадцатый выход первого местного устройства управления соединен с девятым входом второго блока вычисления невязок семнадцатый выход первого местного устройства управления соединен с восьмым входом второго блока вычисления невязок, восемнадцатый выход первого местного устройства управления соединен с седьмым входом второго блока вычисления невязок, первые выходы первого местного устройства управления являются пятыми выходами блока поиска позиций ошибок, вторые выходы первого местного устройства управления являются первыми выходами блока поиска позиций ошибок, первые выходы двенадцатого коммутатора соединены с первыми входами первого регистра-защелки, вторые выходы двенадцатого коммутатора соединены со вторыми входами первого регистра-защелки, третьи выходы двенадцатого коммутатора соединены с третьими входами первого регистра-защелки, вторые выходы первого регистра-защелки соединены с десятыми входами первого блока вычисления невязок, десятыми входами второго блока вычисления невязок и являются вторыми выходами блока поиска позиций ошибок, первые выходы первого регистра-защелки являются третьими выходами блока поиска позиций ошибок, третьи выходы первого регистра-защелки являются четвертыми выходами блока поиска позиций ошибок, причем блок вычисления невязок содержит тринадцатый, четырнадцатый и пятнадцатый коммутаторы, второй регистр-защелку, третий регистр-защелку, второй сумматор элементов поля Галуа, третий сумматор элементов поля Галуа, первый инвертор элементов поля Галуа, первый перемножитель элементов поля Галуа, вторую схему сравнения кодов, первый селектор нулевого элементов поля Галуа, первый логический элемент И, второй логический элемент И, логический элемент ИЛИ-НЕ, D-триггер, причем первые входы тринадцатого коммутатора являются первыми входами блока вычисления невязок, вторые входы тринадцатого коммутатора являются вторыми входами блока вычисления невязок, первые входы четырнадцатого коммутатора являются третьими входами блока вычисления невязок, вторые входы четырнадцатого коммутатора являются четвертыми входами блока вычисления невязок, первый вход пятнадцатого коммутатора является пятым входом блока вычисления невязок, второй вход пятнадцатого коммутатора является шестым входом блока вычисления невязок, третий вход тринадцатого коммутатора, третий вход четырнадцатого коммутатора, третий вход пятнадцатого коммутатора являются седьмым входом блока вычисления невязок, выходы тринадцатого коммутатора соединены с первыми входами второго регистра-защелки и вторыми входами второго сумматора элементов поля Галуа, второй вход второго регистра-защелки, второй вход третьего регистра-защелки, второй вход D-триггера являются восьмым входом блока вычисления невязок, выходы второго регистра-защелки соединены с первыми входами второго сумматора элементов поля Галуа и являются вторыми выходами блока вычисления невязок, выходы второго сумматора элементов поля Галуа соединены со входами первого инвертора элементов поля Галуа, выходы первого инвертора элементов поля Галуа соединены с первыми входами первого перемножителя элементов поля Галуа, выходы первого перемножителя элементов поля Галуа соединены со вторыми входами второй схемы сравнения кодов и являются четвертыми выходами блока вычисления невязок, первые входы второй схемы сравнения кодов являются десятыми входами блока вычисления невязок, выход второй схемы сравнения кодов соединен с первым входом первого логического элемента И, выход первого логического элемента И является пятым выходом блока вычисления невязок, выходы четырнадцатого коммутатора соединены с первыми входами третьего регистра-защелки и вторыми входами третьего сумматора элементов поля Галуа, выходы третьего регистра-защелки соединены с первыми входами третьего сумматора элементов поля Галуа и являются первыми выходами блока вычисления невязок, выходы третьего сумматора элементов поля Галуа соединены со входами первого селектора нулевого элемента поля Галуа и вторыми входами перемножителя элементов поля Галуа, выход первого селектора нулевого элемента поля Галуа соединен с первым входом второго логического элемента И, второй вход второго логического элемента И является девятым входом блока вычисления невязок, выход второго логического элемента И соединен с первым входом логического элемента ИЛИ-НЕ, выход пятнадцатого коммутатора соединен со вторым входом логического элемента ИЛИ-НЕ и первым входом D-триггера, выход D-триггера соединен с третьим входом логического элемента ИЛИ-НЕ, выход логического элемента ИЛИ-НЕ соединен со вторым входом первого логического элемента И и является третьим выходом блока вычисления невязок, причем блок подсчета невязок содержит первый блок вентилей, третий блок памяти с произвольным доступом, схему инкремента, третью схему сравнения кодов, шестнадцатый коммутатор, четвертый регистр-защелку, третий логический элемент И, четвертый логический элемент И, причем второй вход первого блока вентилей и третий вход шестнадцатого коммутатора являются первым входом блока подсчета невязок, выходы первого блока вентилей соединены с первыми входами третьего блока памяти с произвольным доступом, выходы третьего блока памяти с произвольным доступом соединены с первыми входами схемы инкремента, выходы схемы инкремента соединены с первыми входами первого блока вентилей и первыми входами третьей схемы сравнения кодов, вторые входы третьей схемы сравнения кодов соединены с шиной константы 't', выход третьей схемы сравнения кодов соединен с первым входом третьего логического элемента И, выход третьего элемента логическое И является первым выходом блока подсчета невязок, первые входы шестнадцатого коммутатора являются вторыми входами блока подсчета невязок, выходы шестнадцатого коммутатора соединены со вторыми входами третьего блока памяти с произвольным доступом, входы четвертого регистра-защелки являются третьими входами блока подсчета невязок, выходы четвертого регистра-защелки соединены со вторыми входами шестнадцатого коммутатора и являются вторыми выходами блока подсчета невязок, первый вход четвертого логического элемента И является четвертым входом блока подсчета невязок, второй вход четвертого логического элемента И является пятым входом блока подсчета невязок, выход четвертого логического элемента И соединен со вторым входом схемы инкремента и вторым входом третьего логического элемента И.

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

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

Для каждого кодового слова таблица перестановок формируется блоком сортировки позиций символов, в котором она хранится необходимое время. Эта таблица используется для формирования адресов памяти при записи результатов работы блока дискретного преобразования Фурье в блок поиска позиций ошибок веса t+1. Последовательное чтение данных из памяти в блоке поиска позиций ошибок формирует поток данных, упорядоченный в соответствии с надежностью символов кодового слова. В результате достаточно обработать небольшую часть этого потока, чтобы найти позиции ошибочных символов. Это значительно ускоряет работу заявляемого устройства декодирования.

На фиг.1 приведена функциональная схема предлагаемого устройства декодирования PC-кода. На фиг.2 изображена функциональная схема блока сортировки позиций символов; на следующей фиг.3 - функциональная схема одного из его основных блоков: блока памяти отсортированных позиций. На фиг.4 приведена функциональная схема блока поиска позиций ошибок, на следующих фиг.5-6 - функциональные схемы его основных блоков: блока вычисления невязок (фиг.5), блока подсчета невязок (фиг.6). На фиг.7 показана функциональная схема блока дискретного преобразования Фурье, на следующей фиг.8 - функциональная схема одного из его основных блоков: модуля дискретного преобразования Фурье многочлена Λ^(2t)(х). На фиг.9 изображена временная диаграмма обработки кодовых слов предлагаемым устройством декодирования PC-кода. На фиг.10 приведен график с результатами исследований быстродействия заявляемого устройства в канале с аддитивным белым гауссовским шумом (AWGN) и модуляцией BPSK.

В описании устройства и на чертежах используются следующие обозначения:

БВС - блок вычисления синдромов;

БСПС - блок сортировки позиций символов;

БДПФ - блок дискретного преобразования Фурье;

БППО - блок поиска позиций ошибок;

БВЗО - блок вычисления значений ошибок;

БПОП - блок памяти отсортированных позиций;

Ct2 - двоичный счетчик;

DC - дешифратор;

Mux - мультиплексор (коммутатор);

RAM - память с произвольным доступом;

Sub - вычитатель;

МУУ - местное устройство управления;

Inv - инвертор в конечном поле;

Rg - регистр;

БВ - блок вентилей;

БВН - блок вычисления невязок;

БПН - блок подсчета невязок;

БПК - блок памяти коэффициентов;

m - разрядность элемента расширенного поля Галуа GF(2^m);

n - количество символов в кодовом слове PC-кода;

k - количество информационных символов в кодовом слове;

d - минимальное кодовое расстояние PC-кода, d=r+1;

t - число гарантированно исправляемых ошибок в кодовом слове ;

α - примитивный элемент поля Галуа GF(2^m);

r(x)=r_n-1x^n-1+r_n-2x^n-2+…+r₁x+r₀ - многочлен принятого из канала кодового слова;

с(х)=c_n-1x^n-1+с_п-2x^n-2+…+с₁х+с₀ - многочлен исправленного кодового слова;

S(x) - многочлен синдрома;

Λ^(2t)(х) - многочлен локаторов ошибок после 2t итераций алгоритма Берлекэмпа-Месси;

B^(2t)(x) - вспомогательный многочлен после 2t итераций алгоритма Берлекэмпа-Месси;

L_2t - формальная степень многочлена локаторов ошибок Λ^(2t)(х);

Λ^(2t+2)(x) - многочлен локаторов ошибок, полученный аналитическим продолжением алгоритма Берлекэмпа-Месси еще на 2 итерации;

Δ_2t+1 и Δ_2t+2 - невязки аналитического продолжения алгоритма Берлекэмпа-Месси на 2 итерации;

Λ'(х) - формальная производная многочлена локаторов ошибок;

Ω(x) - многочлен значений ошибок;

{РЕ} - множество позиций ошибок в кодовом слове.

Устройство декодирования PC-кода (фиг.1) содержит: буферную память данных 100, блок вычисления синдромов 200, процессор Галуа 300, блок дискретного преобразования Фурье 400, блок поиска позиций ошибок веса t+1 500, блок сортировки позиций символов 600, блок вычисления значений ошибок 700, первый сумматор элементов поля Галуа 800.

На вход буферной памяти данных 100, вход блока вычисления синдромов 200 поступают символы r_i кодового слова, принятого из канала (сигналы DIn). Выходы буферной памяти данных 100 соединены с первыми входами первого сумматора элементов поля Галуа 800. Выходы блока вычисления синдромов 200 соединены с первыми входами процессора Галуа 300. Первые выходы процессора Галуа 300 (сигналы Control) соединены с первыми входами блока дискретного преобразования Фурье 400. Вторые выходы процессора Галуа 300 (Λ^(2t)(x)) соединены со вторыми входами блока дискретного преобразования Фурье 400. Третьи выходы процессора Галуа 300 (B^(2t)(x)) соединены с третьими входами блока дискретного преобразования Фурье 400. Четвертые выходы процессора Галуа 300 (сигналы Control) соединены с четвертыми входами блока поиска позиций ошибок 500. Пятые выходы процессора Галуа 300 (Ω(х)) соединены с первыми входами блока вычисления значений ошибок 700. Шестые выходы процессора Галуа 300 (Λ'(х)) соединены со вторыми входами блока вычисления значений ошибок 700. Седьмые выходы процессора Галуа 300 ({РЕ}) соединены с третьими входами блока вычисления значений ошибок 700.

Вторые выходы блока дискретного преобразования Фурье 400 (сигналы State) соединены с третьими входами процессора Галуа 300. Третьи выходы блока дискретного преобразования Фурье 400 ({РЕ}) соединены с четвертыми входами процессора Галуа 300. Четвертые выходы блока дискретного преобразования Фурье 400 (C_i|D_i) соединены с первыми входами блока поиска позиций ошибок 500. Пятый выход блока дискретного преобразования Фурье 400 (Mskl) соединен со вторым входом блока поиска позиций ошибок 500. Шестые выходы блока дискретного преобразования Фурье 400 (A_i) соединены с третьими входами блока поиска позиций ошибок 500.

Первые выходы блока поиска позиций ошибок 500 (сигналы State) соединены с пятыми входами процессора Галуа 300. Вторые выходы блока поиска позиций ошибок 500 (Δ) соединены с шестыми входами процессора Галуа 300. Третьи выходы блока поиска позиций ошибок 500 (A_i1) соединены с седьмыми входами процессора Галуа 300. Четвертые выходы блока поиска позиций ошибок 500 (C_i1|D_i1) соединены с восьмыми входами процессора Галуа 300.

Первые входы блока сортировки позиций символов 600 (сигналы SoftIn) являются входами оценок надежности символов данных устройства декодирования кодов Рида-Соломона. Оценка надежности представляется двоичным числом без знака с фиксированной точкой. Большее значение числа соответствует большей надежности символов кодового слова.

Пятые выходы блока поиска позиций ошибок 500 ({РЕ'}) соединены со вторыми входами блока сортировки позиций символов 600. Первые выходы блока дискретного преобразования Фурье 400 (AddrR1) соединены с третьими входами блока сортировки позиций символов 600. Первые выходы блока сортировки позиций символов 600 ({РЕ}) соединены со вторыми входами процессора Галуа 300. Вторые выходы блока сортировки позиций символов 600 (AddrW) соединены с пятыми входами блока поиска позиций ошибок 500.

Выходы блока вычисления значений ошибок 700 соединены со вторыми входами первого сумматора элементов поля Галуа 800. Выходы первого сумматора элементов поля Галуа 800 являются выходами данных устройства декодирования кодов Рида-Соломона (сигналы DOut).

Блок сортировки позиций символов 600 (фиг.2) содержит первую схему сравнения кодов 610, первый блок памяти отсортированных позиций 620.1, второй блок памяти отсортированных позиций 620.2, третий блок памяти отсортированных позиций 620.3, четвертый блок памяти отсортированных позиций 620.4, пятый блок памяти отсортированных позиций 620.5, первый коммутатор 630.1, второй коммутатор 630.2, третий коммутатор 670.1, четвертый коммутатор 670.2, пятый коммутатор 670.3, шестой коммутатор 670.4, седьмой коммутатор 670.5, первый счетчик 640, второй счетчик 650.1, третий счетчик 650.2, первый дешифратор 660.1, второй дешифратор 660.2.

Первые входы первой схемы сравнения кодов 610 (сигналы SoftIn) являются первыми входами блока сортировки позиций символов, а вторые входы первой схемы сравнения кодов соединены с шиной константы Thres. Выход первой схемы сравнения кодов 610 соединен со вторым входом первого блока памяти отсортированных позиций 620.1, со вторым входом второго блока памяти отсортированных позиций 620.2, со вторым входом третьего блока памяти отсортированных позиций 620.3, со вторым входом четвертого блока памяти отсортированных позиций 620.4 и со вторым входом пятого блока памяти отсортированных позиций 620.5. Первые выходы первого счетчика 640 соединены с первыми входами первого блока памяти отсортированных позиций 620.1, с первыми входами второго блока памяти отсортированных позиций 620.2, с первыми входами третьего блока памяти отсортированных позиций 620.3, с первыми входами четвертого блока памяти отсортированных позиций 620.4 и с первыми входами пятого блока памяти отсортированных позиций 620.5. Второй выход первого счетчика 640 соединен со входом второго счетчика 650.1. Выходы второго счетчика 650.1 соединены со входами первого дешифратора 660.1. Первый выход первого дешифратора 660.1 соединен с третьим входом первого блока памяти отсортированных позиций 620.1. Второй выход первого дешифратора 660.1 соединен с третьим входом второго блока памяти отсортированных позиций 620.2. Третий выход первого дешифратора 660.1 соединен с третьим входом третьего блока памяти отсортированных позиций 620.3. Четвертый выход первого дешифратора 660.1 соединен с третьим входом четвертого блока памяти отсортированных позиций 620.4. Пятый выход первого дешифратора 660.1 соединен с третьим входом пятого блока памяти отсортированных позиций 620.5. Выходы первого блока памяти отсортированных позиций 620.1 соединены со вторыми входами первого коммутатора 630.1 и четвертыми входами второго коммутатора 630.2. Выходы второго блока памяти отсортированных позиций 620.2 соединены с третьими входами первого коммутатора 630.1 и пятыми входами второго коммутатора 630.2. Выходы третьего блока памяти отсортированных позиций 620.3 соединены с четвертыми входами первого коммутатора 630.1 и первыми входами второго коммутатора 630.2. Выходы четвертого блока памяти отсортированных позиций 620.4 соединены с пятыми входами первого коммутатора 630.1 и вторыми входами второго коммутатора 630.2. Выходы пятого блока памяти отсортированных позиций 620.5 соединены с первыми входами первого коммутатора 630.1 и третьими входами второго коммутатора 630.2. Выходы третьего счетчика 650.2 соединены с шестыми входами первого коммутатора 630.1, с шестыми входами второго коммутатора 630.2 и входами второго дешифратора 660.2. Первый выход второго дешифратора 660.2 соединен с третьим входом седьмого коммутатора 670.5, второй выход второго дешифратора 660.2 соединен с третьим входом третьего коммутатора 670.1. Третий выход второго дешифратора 660.2 соединен с третьим входом четвертого коммутатора 670.2. Четвертый выход второго дешифратора 660.2 соединен с третьим входом пятого коммутатора 670.3. Пятый выход второго дешифратора 660.2 соединен с третьим входом шестого коммутатора 670.4. Первые входы третьего 670.1, четвертого 670.2, пятого 670.3, шестого 670.4 и седьмого 670.5 коммутаторов (сигналы AdR1) являются третьими входами блока сортировки позиций символов 600. Вторые входы третьего 670.1, четвертого 670.2, пятого 670.3, шестого 670.4 и седьмого 670.5 коммутаторов (сигналы AdR2) являются вторыми входами блока сортировки позиций символов 600. Выходы третьего коммутатора 670.1 соединены с четвертыми входами Adr первого блока памяти отсортированных позиций 620.1. Выходы четвертого коммутатора 670.2 соединены с четвертыми входами Adr второго блока памяти отсортированных позиций 620.2. Выходы пятого коммутатора 670.3 соединены с четвертыми входами Adr третьего блока памяти отсортированных позиций 620.3. Выходы шестого коммутатора 670.4 соединены с четвертыми входами Adr четвертого блока памяти отсортированных позиций 620.4. Выходы седьмого коммутатора 670.5 соединены с четвертыми входами Adr пятого блока памяти отсортированных позиций 620.5. Выходы первого коммутатора 630.1 (сигналы DOR1) являются вторыми выходами блока сортировки позиций символов. Выходы второго коммутатора 630.2 (сигналы DOR2) являются первыми выходами блока сортировки позиций символов.

Все используемые в блоке 600 счетчики - двоичные: счетчик 640 работает с коэффициентом пересчета n, счетчики 650 работают с коэффициентом перечета 5.

Дешифраторы 660 имеют инверсные выходы. На i-х выходах дешифраторов (i=1,…,5) появляются значения логического ноля (активный уровень), когда на их входы подаются значения «i-1».

Все коммутаторы в блоке 600-m-разрядные. На выходы коммутаторов 630 подаются значения их «i-х» входов (i=1,…,5), если на их шестые входы подаются значения «i-1». На выходы коммутаторов 670 подаются значения их первых входов, если на их третьи входы подаются значения логического ноля.

Блок памяти отсортированных позиций (фиг.3) содержит первый блок памяти с произвольным доступом 621.1, второй блок памяти с произвольным доступом 621.2, первый логический элемент И-НЕ 622, второй логический элемент И-НЕ 627, четвертый счетчик 623.1, пятый счетчик 623.2, восьмой коммутатор 624.1, девятый коммутатор 624.2, десятый коммутатор 625.1, одиннадцатый коммутатор 625.2 и вычитатель 626.

Первые входы первого блока памяти с произвольным доступом 621.1, первые входы второго блока памяти с произвольным доступом 621.2 являются первыми входами DI блока памяти отсортированных позиций. Первый вход первого логического элемента И-НЕ 622, первый вход второго логического элемента И-НЕ 627, третий вход восьмого коммутатора 624.1, третий вход девятого коммутатора 624.2 являются третьим входом блока памяти отсортированных позиций. Второй вход первого логического элемента И-НЕ 622, второй вход второго логического элемента И-НЕ 627 являются вторым входом S блока памяти отсортированных позиций. Выход первого логического элемента И-НЕ 622 соединен со вторым входом первого блока памяти с произвольным доступом 621.1 и входом четвертого счетчика 623.1. Выходы четвертого счетчика 623.1 соединены с первыми входами восьмого коммутатора 624.1, вторыми входами одиннадцатого коммутатора 625.2 и первыми входами вычитателя 626. Выходы восьмого коммутатора 624.1 соединены с третьими входами А первого блока памяти с произвольным доступом 621.1. Выходы первого блока памяти с произвольным доступом 621.1 соединены с первыми входами десятого коммутатора 625.1. Выход второго логического элемента И-НЕ 627 соединен со вторым входом второго блока памяти с произвольным доступом 621.2 и входом пятого счетчика 623.2. Выходы пятого счетчика 623.2 соединены с первыми входами девятого коммутатора 624.2. Выходы девятого коммутатора 624.2 соединены с третьими входами А второго блока памяти с произвольным доступом 621.2. Выходы второго блока памяти с произвольным доступом 621.2 соединены со вторыми входами десятого коммутатора 625.1. Вторые входы вычитателя 626 и вторые входы восьмого коммутатора 624.1 (сигналы Adr) являются четвертыми входами блока памяти отсортированных позиций, а старший разряд четвертых входов блока памяти отсортированных позиций соединен с третьим входом одиннадцатого коммутатора 625.2. Первые выходы вычитателя 626 соединены со вторыми входами девятого коммутатора 624.2. Второй выход вычитателя 626 соединен с третьим входом десятого коммутатора 625.1. Выходы десятого коммутатора 625.1 соединены с первыми входами одиннадцатого коммутатора 625.2. Выходы одиннадцатого коммутатора 625.2 являются выходами блока памяти отсортированных позиций.

Блоки памяти с произвольным доступом 621 содержат n log₂n-разрядных ячеек. Счетчики 623 - двоичные log₂n-разрядные. Такую же разрядность имеют коммутаторы 624 и 625. Они осуществляют коммутацию с двух направлений, передавая значения своих первых входов на выходы, когда на их третьи входы подается значение логического ноля.

Вычитатель 626 осуществляет вычитание содержимого счетчика 623.1 из значения, поданного на четвертые входы блока 620 (сигналы Adr). На втором выходе вычитателя формируется сигнал заема.

Блок поиска позиций ошибок (фиг.4) содержит первый блок вычисления невязок 510.1, второй блок вычисления невязок 510.2, первый блок подсчета невязок 520.1, второй блок подсчета невязок 520.2, двенадцатый коммутатор 530, первый регистр-защелку 540, блок памяти коэффициентов 550, первое местное устройство управления 560.

Первые входы первого местного устройства управления 560 (сигналы Control) являются четвертыми входами блока поиска позиций ошибок 500. Вторые входы первого местного устройства управления 560 и первые входы блока памяти коэффициентов 550 (сигналы AddrW) являются пятыми входами блока поиска позиций ошибок. Третьи входы блока поиска позиций ошибок 500 (сигналы A_i) являются младшими разрядами вторых входов блока памяти коэффициентов 550. Первые входы блока поиска позиций ошибок 500 являются средними разрядами вторых входов блока памяти коэффициентов 550 (C_i|D_i). Второй вход блока поиска позиций ошибок 500 (Msk1) является старшим разрядом вторых входов блока памяти коэффициентов 550 (Mask1). Младшие разряды первых выходов D_R1 блока памяти коэффициентов 550 (сигналы A'_i) соединены с первыми входами первого блока вычисления невязок 510.1 и с первыми входами второго блока вычисления невязок 510.2. Средние разряды первых выходов D_R1 блока памяти коэффициентов 550 (C'_i|D'_i) соединены с третьими входами первого блока вычисления невязок 510.1 и с третьими входами второго блока вычисления невязок 510.2. Старший разряд первых выходов D_R1 блока памяти коэффициентов 550 (Msk1') соединен с пятым входом первого блока вычисления невязок 510.1 и с пятым входом второго блока вычисления невязок 510.2. Младшие разряды вторых выходов D_R2 блока памяти коэффициентов 550 (А''_i) соединены со вторыми входами первого блока вычисления невязок 510.1 и со вторыми входами второго блока вычисления невязок 510.2. Средние разряды вторых выходов D_R2 блока памяти коэффициентов 550 (С''_i|D''_i) соединены с четвертыми входами первого блока вычисления невязок 510.1 и с четвертыми входами второго блока вычисления невязок 510.2. Старший разряд вторых выходов D_R2 блока памяти коэффициентов 550 (Msk1'') соединен с шестым входом первого блока вычисления невязок 510.1 и с шестым входом второго блока вычисления невязок 510.2.

Первые выходы первого блока вычисления невязок 510.1 (сигналы (C_i1|D_i1)₁) соединены с шестыми входами двенадцатого коммутатора 530. Вторые выходы первого блока вычисления невязок 510.1 ((A_i1)₁) соединены с пятыми входами двенадцатого коммутатора 530. Третий выход первого блока вычисления невязок 510.1 (¬Msk2₁) соединен с четвертым входом первого блока подсчета невязок 520.1. Четвертые выходы первого блока вычисления невязок 510.1 (Δ'₁) соединены с третьими входами первого блока подсчета невязок 520.1. Пятый выход первого блока вычисления невязок 510.1 (SX_i1) соединен с третьим входом местного устройства управления 560. Первый выход первого блока подсчета невязок 520.1 (St₁) соединен с пятым входом первого местного устройства управления 560. Вторые выходы первого блока подсчета невязок 520.1 (Δ''₁) соединены с четвертыми входами двенадцатого коммутатора 530.

Первые выходы второго блока вычисления невязок 510.1 (сигналы (C_i1|D_i1)₂) соединены с первыми входами двенадцатого коммутатора 530. Вторые выходы второго блока вычисления невязок 510.2 ((A_i1)₂) соединены со вторыми входами двенадцатого коммутатора 530. Пятый выход второго блока вычисления невязок 510.2 (SX_i2) соединен с четвертым входом первого местного устройства управления 560. Четвертые выходы второго блока вычисления невязок 510.2 (Δ'₂) соединены с третьими входами второго блока подсчета невязок 520.2. Третий выход второго блока вычисления невязок 510.2 (¬Msk2₂) соединен с четвертым входом второго блока подсчета невязок 520.2. Вторые выходы второго блока подсчета невязок 520.2 (Δ''₂) соединены с третьими входами двенадцатого коммутатора 530. Первый выход второго блока подсчета невязок 520.2 (St₂) соединен с шестым входом первого местного устройства управления 560. Третий выход первого местного устройства управления 560 (CMx₁) соединен с седьмым входом первого блока вычисления невязок 510.1. Четвертый выход первого местного устройства управления 560 (Ld₁) соединен с восьмым входом первого блока вычисления невязок 510.1. Пятый выход первого местного устройства управления 560 (EM₁) соединен с девятым входом первого блока вычисления невязок 510.1. Шестые выходы первого местного устройства управления 560 (AR1) соединены с четвертыми входами A_R1 блока памяти коэффициентов 550. Седьмые выходы первого местного устройства управления 560 (AR2) соединены с третьими входами A_R2 блока памяти коэффициентов 550. Восьмые выходы первого местного устройства управления 560 (AI₁) соединены со вторыми входами первого блока подсчета невязок 520.1. Девятый выход первого местного устройства управления 560 (I₁) соединен с первым входом первого блока подсчета невязок 520.1. Десятый выход местного первого устройства управления 560 (E₁) соединен с пятым входом первого блока подсчета невязок 520.1. Одиннадцатый выход первого местного устройства управления 560 (L) соединен с четвертым входом первого регистра-защелки 540. Двенадцатые выходы первого местного устройства управления 560 (СМх) соединены с седьмыми входами двенадцатого коммутатора 530. Тринадцатый выход первого местного устройства управления 560 (Е₂) соединен с пятым входом второго блока подсчета невязок 520.2. Четырнадцатый выход первого местного устройства управления 560 (I₂) соединен с первым входом второго блока подсчета невязок 520.2. Пятнадцатые выходы первого местного устройства управления 560 (AI₂) соединены со вторыми входами второго блока подсчета невязок 520.2. Шестнадцатый выход первого местного устройства управления 560 (ЕМ₂) соединен с девятым входом второго блока вычисления невязок 510.2. Семнадцатый выход первого местного устройства управления 560 (Ld₂) соединен с восьмым входом второго блока вычисления невязок 510.2. Восемнадцатый выход первого местного устройства управления 560 (СМх₂) соединен с седьмым входом второго блока вычисления невязок 510.2. Первые выходы первого местного устройства управления 560 ({РЕ'}) являются пятыми выходами блока поиска позиций ошибок 500. Вторые выходы первого местного устройства управления 560 (State) являются первыми выходами блока поиска позиций ошибок 500. Первые выходы двенадцатого коммутатора 530 соединены с первыми входами первого регистра-защелки 540. Вторые выходы двенадцатого коммутатора 530 соединены со вторыми входами первого регистра-защелки 540. Третьи выходы двенадцатого коммутатора 530 соединены с третьими входами первого регистра-защелки 540. Вторые выходы первого регистра-защелки 540 (Δ) соединены с десятыми входами первого блока вычисления невязок 510.1, десятыми входами второго блока вычисления невязок 510.2 и являются вторыми выходами блока поиска позиций ошибок 500. Первые выходы первого регистра-защелки 540 (A_i1) являются третьими выходами блока поиска позиций ошибок 500. Третьи выходы первого регистра-защелки 540 (C_i1|D_i1) являются четвертыми выходами блока поиска позиций ошибок 500.

Коммутатор 530 - трехсекционный двунаправленный. Первый и шестой входы коммутатора являются входами первой секции, второй и пятый входы - входами второй секции, третий и четвертый входы - входами третьей секции.

Блок вычисления невязок (фиг.5) содержит тринадцатый 511.1, четырнадцатый 511.2 и пятнадцатый коммутаторы 511.0, второй регистр-защелку 512.1, третий регистр-защелку 512.2, второй сумматор элементов поля Галуа 513.1, третий сумматор элементов поля Галуа 513.2, первый инвертор элементов поля Галуа 514, первый перемножитель элементов поля Галуа 515, вторую схему сравнения кодов 516.1, первый селектор нулевого элемента поля Галуа 516.2, первый логический элемент И 517.2, второй логический элемент И 517.1, логический элемент ИЛИ-НЕ 518, D-триггер 519.

Первые входы тринадцатого коммутатора 511.1 (сигнал A_i ^') являются первыми входами блока вычисления невязок. Вторые входы тринадцатого коммутатора 511.1 (A_i'') являются вторыми входами блока вычисления невязок. Первые входы четырнадцатого коммутатора 511.2 (C'_i(D'_i)) являются третьими входами блока вычисления невязок. Вторые входы четырнадцатого коммутатора 511.2 (С''_i(D''_i)) являются четвертыми входами блока вычисления невязок. Первый вход пятнадцатого коммутатора 511.0 (Msk1') является пятым входом блока вычисления невязок. Второй вход пятнадцатого коммутатора 511.0 (MSk1'') является шестым входом блока вычисления невязок.

Третий вход тринадцатого коммутатора 511.1, третий вход четырнадцатого коммутатора 511.2, третий вход пятнадцатого коммутатора 511.0 являются седьмым входом блока вычисления невязок, на который подается сигнал СМх. Выходы тринадцатого коммутатора 511.1 соединены с первыми входами второго регистра-защелки 512.1 и вторыми входами второго сумматора элементов поля Галуа 513.1. Второй вход второго регистра-защелки 512.1, второй вход третьего регистра-защелки 512.2, второй вход D-триггера 519 являются восьмым входом блока вычисления невязок, на который подается сигнал Ld. Выходы второго регистра-защелки 512.1 (сигналы A_i1) соединены с первыми входами второго сумматора элементов поля Галуа 513.1 и являются вторыми выходами блока вычисления невязок. Выходы второго сумматора элементов поля Галуа 513.1 соединены со входами первого инвертора элементов поля Галуа 514. Выходы первого инвертора элементов поля Галуа 514 соединены с первыми входами первого перемножителя элементов поля Галуа 515. Выходы первого перемножителя элементов поля Галуа 515 (сигналы Δ') соединены со вторыми входами второй схемы сравнения кодов 516.1 и являются четвертыми выходами блока вычисления невязок. Первые входы второй схемы сравнения кодов 516.1 являются десятыми входами блока вычисления невязок, на которые подаются сигналы Δ. Выход второй схемы сравнения кодов 516.1 соединен с первым входом первого логического элемента И 517.1. Выход первого логического элемента И 517.1 (сигнал SX_i) является пятым выходом блока вычисления невязок. Выходы четырнадцатого коммутатора 511.2 соединены с первыми входами третьего регистра-защелки 512.2 и вторыми входами третьего сумматора элементов поля Галуа 513.3. Выходы третьего регистра-защелки 512.2 (C_i1|D_i1) соединены с первыми входами третьего сумматора элементов поля Галуа 513.2 и являются первыми выходами блока вычисления невязок. Выходы третьего сумматора элементов поля Галуа 513.2 соединены со входами первого селектора нулевого элемента поля Галуа 516.2 и вторыми входами первого перемножителя элементов поля Галуа 515. Выход первого селектора нулевого элемента поля Галуа 516.2 соединен с первым входом второго логического элемента И 517.2. Второй вход второго логического элемента И 517.2 является девятым входом блока вычисления невязок, на который подается сигнал ЕМ. Выход второго логического элемента И 517.2 соединен с первым входом логического элемента ИЛИ-НЕ 518. Выход пятнадцатого коммутатора 511.0 соединен со вторым входом логического элемента ИЛИ-НЕ 518 и первым входом D-триггера 519. Выход D-триггера 519 соединен с третьим входом логического элемента ИЛИ-НЕ 518. Выход логического элемента ИЛИ-НЕ 518 (¬Msk2) соединен со вторым входом первого логического элемента И 517.1 и является третьим выходом блока вычисления невязок.

Регистры-защелки 512 и D-триггер 519 принимают информацию при активном сигнале Ld, который подается на их вторые входы.

Блок подсчета невязок (фиг.6) содержит первый блок вентилей 521, третий блок памяти с произвольным доступом 522, схему инкремента 523, третью схему сравнения кодов 524, третий логический элемент И 525, шестнадцатый коммутатор 526, четвертый регистр-защелку 527, четвертый логический элемент И 528.

Второй вход первого блока вентилей и третий вход шестнадцатого коммутатора являются первым входом блока подсчета невязок, на который подается сигнал I. Выходы первого блока вентилей соединены с первыми входами DI третьего блока памяти с произвольным доступом 522. Выходы третьего блока памяти с произвольным доступом 522 соединены с первыми входами схемы инкремента 523. Выходы схемы инкремента 523 соединены с первыми входами первого блока вентилей 521 и первыми входами третьей схемы сравнения кодов 524. Вторые входы третьей схемы сравнения кодов 524 соединены с шиной константы 't'. Выход третьей схемы сравнения кодов 524 соединен с первым входом третьего логического элемента И 525. Выход третьего элемента логическое И 525 является первым выходом блока подсчета невязок, на котором формируется сигнал St. Первые входы шестнадцатого коммутатора 526 являются вторыми входами блока подсчета невязок, на который подаются сигналы AI. Выходы шестнадцатого коммутатора 526 соединены со вторыми входами А третьего блока памяти с произвольным доступом 522. Входы четвертого регистра-защелки 527 являются третьими входами блока подсчета невязок, на который подаются сигналы Δ'. Выходы четвертого регистра-защелки 527 (сигналы Δ''_n) соединены со вторыми входами шестнадцатого коммутатора 526 и являются вторыми выходами блока подсчета невязок. Первый вход четвертого логического элемента И 528 является четвертым входом блока подсчета невязок, на который подается сигнал ¬Msk2. Второй вход четвертого логического элемента И 528 является пятым входом блока подсчета невязок, на который подается сигнал Е. Выход четвертого логического элемента И 528 соединен со вторым входом схемы инкремента 523 и вторым входом третьего логического элемента И 525.

Блок вентилей 521 передает информацию с первых входов на выходы, когда на второй его вход подается логический ноль, в противном случае на его выходах формируются нули.

Блок дискретного преобразования Фурье (фиг.7) содержит второе местное устройство управления 410, первый модуль дискретного преобразования Фурье многочлена Λ^(2t)(х) 420.1, второй модуль дискретного преобразования Фурье многочлена В^(2t)(х) 420.2, семнадцатый коммутатор 430, второй инвертор элементов поля Галуа 440, второй перемножитель двух элементов поля Галуа 450, восемнадцатый двухвходовый коммутатор 460, умножитель на α 470, пятый регистр-защелку 480, работающую по фронту тактового сигнала; шестой двоичный счетчик номеров позиций принятого слова 490 с коэффициентом пересчета n.

Первые входы второго местного устройства управления 410 являются первыми входами блока дискретного преобразования Фурье 400, на которые подаются сигналы Control. Первые выходы второго местного устройства управления 400 являются вторыми выходами блока дискретного преобразования Фурье 400, на которые выдаются сигналы State. Вторые выходы второго местного устройства управления 410 являются третьими выходами блока дискретного преобразования Фурье 400, на которые выдаются сигналы {РЕ}. Третьи выходы второго местного устройства управления 410 соединены со вторыми входами первого модуля дискретного преобразования Фурье 420.1 и со вторыми входами второго модуля дискретного преобразования Фурье 420.2. Четвертый выход второго местного устройства управления 410 соединен с третьим входом семнадцатого коммутатора 430 и с третьим входом восемнадцатого коммутатора 460. Первые входы первого модуля дискретного преобразования Фурье 420.1 и второго модуля дискретного преобразования Фурье 420.2 являются вторыми и третьими входами блока дискретного преобразования Фурье 400, на которые подаются сигналы Λ(х), В(х). Первые выходы первого модуля дискретного преобразования Фурье 420.1 (сигналы Λ(α^-1)) соединены с первыми входами семнадцатого коммутатора 430. Второй выход первого модуля дискретного преобразования Фурье 420.1 (sel0) соединен с третьим входом второго местного устройства управления 410 и первым входом восемнадцатого коммутатора 460. Первые выходы второго модуля дискретного преобразования Фурье 420.2 (В(α^-1)) соединены со вторыми входами семнадцатого коммутатора 430. Второй выход второго модуля дискретного преобразования Фурье 420.2 (sel0) соединен со вторым входом восемнадцатого коммутатора 460. Первые выходы семнадцатого коммутатора 430 соединены со входами второго инвертора элементов поля Галуа 440. Вторые выходы семнадцатого коммутатора соединены со вторыми входами второго перемножителя элементов поля Галуа 450. Выходы второго инвертора элементов поля Галуа 440 соединены с первыми входами второго перемножителя элементов поля Галуа 450. Выходы второго перемножителя элементов поля Галуа являются четвертыми выходами блока дискретного преобразования Фурье 400, на которые выдаются сигналы (C_i|D_i). Выход восемнадцатого коммутатора 460 является пятым выходом блока дискретного преобразования Фурье 400, на который выдается сигнал Msk1. Выходы шестого двоичного счетчика 490 соединены со вторыми входами второго местного устройства управления 410 и являются первыми выходами блока дискретного преобразования Фурье 400, на которые выдаются сигналы AddrR1. Выходы умножителя на α 470 соединены со входами пятого регистра-защелки 480. Выходы пятого регистра-защелки 480 соединены со входами умножителя на α 470 и являются шестыми выходами блока дискретного преобразования Фурье 400, на которые выдаются сигналы A_i.

Семнадцатый коммутатор 430 - перекресный. Когда сигнал на третьем входе - активный, коммутатор работает в режиме перекрестной передачи: значения его первых входов подаются на вторые выходы, значения его вторых входов подаются на первые выходы. При неактивном сигнале на третьем входе коммутатор работает в режиме прямой передачи.

Модуль дискретного преобразования Фурье (фиг.8) содержит второй блок вентилей 421, шестой, седьмой, восьмой, …, t+7 регистры-защелки, работающие по фронту тактового импульса, 422.0 - 422.t+1, четвертый сумматор элементов поля Галуа на t+2 входа 423, второй селектор нулевого элемента поля Галуа 424, первый, второй, …, t+1 умножители на постоянные коэффициенты в поле Галуа 425.1 - 425.t+1, первый, второй, …, t+1 блоки логических элементов ИЛИ 426.1-426.t+1.

Первые входы второго блока вентилей 421 являются первыми входами модуля дискретного преобразования Фурье, на которые подаются сигналы Λ(х). Второй вход второго блока вентилей 421 (сигнал enable) подключен к шине loc_contr, представляющей вторые входы БДПФ 400. Выходы второго блока вентилей 421 соединены с первыми входами шестого регистра-защелки 422.0, вторыми входами первого, второго, …, t+1 блоков логических элементов ИЛИ 426.1, …, 426.t+1. Вторые входы шестого, седьмого, восьмого, …, t+7 регистров-защелок подключены к шине loc_contr (сигналы c₀…c_t+1). Третьи входы шестого, седьмого, восьмого, …, t+7 регистров-защелок подключены к шине loc_contr (сигнал clear). Выходы первого, второго, …, t+1 блоков логических элементов ИЛИ 426.1,…, 426.t+1 соединены с первыми входами седьмого, восьмого, …, t+7 регистров-защелок 422.1, …, 425.t+1 соответственно. Выходы шестого регистра-защелки 422.0 соединены с первыми входами четвертого сумматора элементов поля Галуа 423. Выходы седьмого, восьмого, …, t+7 регистров-защелок 422.1, …, 425.t+1 соединены соответственно со вторыми, третьими, …, t+2 входами четвертого сумматора элементов поля Галуа 423 и входами первого, второго, …, t+1 умножителя на постоянные коэффициенты в поле Галуа 425.1, …, 425.t+1, соответственно. Выходы первого, второго, …, t+1 умножителя на постоянные коэффициенты в поле Галуа 425.1…425.t+1 соединены с первыми входами первого, второго, …, t+1 блоков логических элементов ИЛИ 426.1, …, 426.t+1 соответственно. Выходы четвертого сумматора элементов поля Галуа 423 соединены со входами второго селектора нулевого элемента поля Галуа 424 и являются первыми выходами модуля дискретного преобразования Фурье, на которые выдаются сигналы Λ(w). Выход второго селектора нулевого элемента поля Галуа 424 является вторым выходом модуля дискретного преобразования Фурье, на который выдается сигнал sel0.

Все линии связи, соединяющие блоки на фиг.1-8, по которым передаются данные в виде элементов поля Галуа, являются m-разрядными.

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

Сумматоры элементов поля, умножители на постоянные коэффициенты и блоки нахождения обратного элемента поля могут быть реализованы известным образом, в частности, сумматоры могут быть реализованы на m двухвходовых элементах ИСКЛЮЧАЮЩЕЕ-ИЛИ (сумматорах по модулю 2), умножители на постоянные коэффициенты могут быть реализованы на многовходовых элементах ИСКЛЮЧАЮЩЕЕ-ИЛИ, блоки нахождения обратного элемента могут быть реализованы табличным способом.

Процедура декодирования, выполняемая заявляемым устройством, обеспечивает исправление t+1 ошибки в кодовом PC-кода с минимальным кодовым расстоянием d=2t+1 путем аналитического продолжения алгоритма Берлекэмпа-Месси еще на две итерации. Это продолжение дает:

где δ_k=1, если Δ_k≠0 и 2L_k-1≤k-1, или δ_k=0 в противном случае. L_k - формальная степень многочлена локаторов ошибок Λ^(k)(х), В^(k)(х) - вспомогательный многочлен.

Каждой паре неизвестных невязок Δ_2+t1 и Δ_2t+2. соответствует многочлен Λ^(2t+2)(х). По определению многочлен локаторов ошибок Λ(х) обращается в нуль, когда х принимает значения, обратные к локаторам ошибочных символов. Представляют интерес такие многочлены Λ^(2t+2)(х), которые имеют степень t+1 и имеют точно t+1 корень в GF(q). Множество допустимых корней многочлена Λ^(2t+2)(x) составляет {α⁰, α^-1, α^-2, …, α^-(n-2), α^-(n-1)} (α - примитивный элемент поля GF(q)). Подставляя это множество в уравнение (1), можно получить следующее:

где Λ^(2t)(α^-i) и В^(2t)(α^-i) - компоненты дискретного преобразования Фурье многочленов Λ^(2t)(х) и В^(2t)(х).

В случае наличия в кодовом слове конфигурации ошибок веса t+1 ровно t+1 правых частей уравнений системы (2) для некоторого значения пары невязок Δ_2t+1 и Δ_2t+2 обращаются в 0. Для определения позиций этих ошибочных символов необходимо найти соответствующую пару невязок и зафиксировать номера i уравнений системы (2) с правыми частями, обратившимися в нуль.

Приравняв левые части уравнений системы (2) нулю, можно получить следующую систему уравнений от двух неизвестных Δ_2t+1 и Δ_2t+2:

Подмножества из ровно t+1 совместных уравнений системы (3) будут соответствовать искомым комбинациям ошибок веса t+1, значения номеров уравнений i дадут позиции ошибок в кодовом слове.

Эти подмножества могут быть найдены следующим образом [3, 4]. Фиксируется одно из уравнений системы (3) (обозначим его номер i). К нему присоединяется одно из оставшихся уравнений (пусть его номер будет j). Для этих двух уравнений с двумя неизвестными находится возможное значение невязки . Затем к первому уравнению последовательно присоединяются другие оставшиеся уравнения. Для всех таких пар уравнений также вычисляются возможные значения невязки . Если среди всех полученных значений невязки есть t одинаковых, равных Δ_2t+1, это говорит о том, что зафиксированное уравнение с номером i входит в искомое подмножество уравнений (и определяет позицию первой ошибки). Значения j, соответствующие условию , дадут позиции еще t ошибок. В процессе поиска перебираются все возможные значения i.

Формальное описание процедуры декодирования основывается на нижеприведенных Теореме, Следствии и Утверждении [3, 4], приведенных ниже без доказательств.

Теорема: Пусть Λ^(2t)(х), В^(2t)(х) и L_2t получены после 2t итераций алгоритма Берлекэмпа-Месси. Если L_2t<t или L_2t>t+1, то тогда в принятом слове не может быть t+1 ошибок.

Если L_2t=t, то тогда неизвестные невязки, соответствующие t+1 ошибкам, могут быть найдены из следующей системы уравнений:

где

Если L_2t=t+1, то тогда невязки могут быть найдены из системы:

где

Следствие: Если L_2t=t, то последовательности значений Δ_2t+1, полученные для всех пар i и j уравнений системы (4), будут иметь следующий вид:

Если L_2t=t+1, то последовательности значений Δ_2t+1, полученные из системы (6), будут иметь следующий вид:

Обозначим через Cnt(S) оператор подсчета различных значений элементов последовательности S в поле GF(q). Этот оператор формирует вектор W размерности q: i-ая компонента вектора (i=0 …, q-2) соответствует элементу поля αⁱ∈GF(q), последняя компонента (i=q-1) соответствует нулевому элементу поля GF(q). Тогда справедливо следующее утверждение.

Утверждение: Пусть Δ - множество значений Δ_2t+1 такое, что полином Λ^(2t+2)(x) имеет точно t+1 допустимых корней в поле GF(q). Пусть W_i=Cnt(S_i); i=0, …, n-1-t; Р(α^-i)≠0. Тогда множество Δ состоит из всех значений αⁱ, удовлетворяющих условию w_i,j=t для всех i=0, …, n-1-t, Р(α^-i)≠0 и l=0, …, q-2.

Значение i для найденной невязки Δ_2t+1 дает позицию (i₁=i) первой ошибки. Значения j, удовлетворяющие условию дают позиции (j₁, j₂, …, j_t) остальных ошибок. Тогда локатор первой ошибки будет , и локаторы остальных ошибок будут , …, .

После нахождения невязки Δ_2t+1 невязку Δ_2t+2 можно легко вычислить, используя (4)

или (6)

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

1) Вычисление полинома синдромов S(x).

2) Получение полинома локаторов Λ^(2t)(х), вспомогательного полинома В^(2t)(х) и формальной степени полинома локаторов L_2t с использованием алгоритма Берлекэмпа-Месси.

3) Вычисление преобразования Фурье полиномов Λ^(2t)(x) и В^(2t)(х), когда L_2t=t или L_2t=t+1.

4а) Вычисление коэффициентов C_i=В^(2t)(α^-i)/Λ^(2t)(α^-i), когда L_2t=t, или D_i=Λ^(2t)(α^-i)/(В^(2t)(α^-i)·α^-2i), когда L_2t=t+1.

4b) Вычисление последовательностей S_i возможных значений невязки Δ_2t+1 для каждого значения i∈{0,…,n-1-t} (j=i+1,…,n-1), подсчет значений W_i для каждой последовательности и фиксация значения Δ_2t+1, которое встречается точно t раз в какой-то из этих последовательностей (w_i,l=t), где

когда L_2t=t, или

когда L_2t=t+1 (L - массив номеров позиций символов принятого кодового слова, упорядоченных (может быть частично) по возрастанию надежности символов, n_c≤n-1-t).

4с) Повторное вычисление последовательностей S_i для найденного значения i и фиксация позиций ошибок в моменты времени равенства невязки Δ_2t+1 значениям .

5) Получение полинома Λ^(2t+2)(x), вычисление значений ошибок и их исправление.

При такой организации перебора (12, 13) неизвестная невязка находится при малых значениях i.

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

Заявляемое устройство декодирования PC-кодов содержит: буферную память данных 100, блок вычисления синдромов 200, процессор Галуа 300, блок дискретного преобразования Фурье 400, блок поиска позиций ошибок веса t+1 500, блок сортировки позиций символов 600, блок вычисления значений ошибок 700, первый сумматор элементов поля Галуа 800.

Устройство обрабатывает входные данные, представляющие собой последовательность n m-разрядных символов кодового слова {r_i}, принятого из канала, которые сопровождаются значениями их надежности {rel_i}. При этом оно выполняет описанную выше процедуру декодирования. На выход устройства выдается последовательность n m-разрядных символов кодового слова с исправленными ошибками {c_i}.

Буферная память данных 100 (фиг.1) предназначена для временного хранения принятых из канала символов исправляемых кодовых слов. Может быть реализована известным образом на основе двухпортовой RAM.

Блок вычисления синдромов 200 выполняет 1-й этап процедуры декодирования, заключающийся в вычислении многочлена синдрома S(x) принятого кодового слова, может быть реализован известным образом по схеме Горнера [4, 5].

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

Процессор Галуа 300 - специализированный процессор, выполняющий операции в конечном поле Галуа, может быть реализован известным образом на основе RISC-архитектуры.

Процессор Галуа 300 реализует алгоритм Берлекэмпа-Месси [4, 5], вычисляя в соответствии с ним многочлены Λ^(2t)(x) и В^(2t)(х) за 2t итераций (2-ой этап процедуры декодирования).

Кроме того, на основе информации, полученной от блока поиска позиций ошибок веса t+1 500 (i₁∈{РЕ}, Δ ( или Δ=Δ_2t+1), или он вычисляет значение Δ_2t+2 по формуле (10) или (11) и затем Λ^(2t+2)(x) (выполнив еще две итерации алгоритма Берлекэмпа-Месси с невязками Δ_2t+1 и Δ_2t+2). Используя многочлены Λ(х)=Λ^(2t+2)(х) и S(x), процессор Галуа 300 вычисляет многочлен значений ошибок Ω(х)=Λ(x)·S(x)modx^d-1 и формальную производную Λ'(х) многочлена локаторов Λ(х) с последующей загрузкой полученных многочленов вместе с найденными позициями ошибок {РЕ} в блок вычисления значений ошибок 700. Таким образом, выполняется начало 5-го этапа процедуры декодирования.

Кроме этого, процессор Галуа 300 управляет БДПФ 400 и БППО 500 (с использованием сигналов управления Control). Процессор Галуа устанавливает режим работы БДПФ 400, он же загружает в него коэффициенты многочленов Λ^(2t)(x) и В^(2t)(х). Процессор Галуа контролирует состояние БДПФ (сигналы состояния State) и выгружает из него значения позиций ошибок веса меньшего или равного t. Также процессор Галуа контролирует состояние БППО (сигналы состояния State) и выгружает из него значения позиций ошибок веса t+1 (пропуская их предварительно через таблицу перестановок L блока БСПС 600).

Блок ДПФ 400 вычисляет преобразование Фурье многочленов Λ^(2t)(х) и В^(2t)(х) (3-ий этап процедуры декодирования). Кроме того, в зависимости от режима работы он вычисляет коэффициенты C_i или D_i, а также коэффициенты A_i=αⁱ (этап 4а процедуры декодирования). Эти коэффициенты загружаются в память блока БППО 500, адресуемую с помощью таблицы перестановок L блока БСПС 600. Блок ДПФ также вычисляет величины, обратные к корням полинома Λ^(2t)(х), и контролирует их число, если L_2t≤t.

Блок поиска позиций ошибок веса t+1 500 в зависимости от режима работы анализирует систему (4) с коэффициентами C_i или систему (6) с коэффициентами D_i. Он находит позиции ошибок веса t+1 и соответствующие им значения Δ, , или . Таким образом выполняются этапы 4b и 4с процедуры декодирования.

Блок вычисления значений ошибок 700, используя многочлены Ω(х) и Λ'(х), вычисляет значения ошибок в найденных позициях ошибок {РЕ}. Он может быть реализован известным образом с использованием формулы Форни [4, 5]. Значения ошибок суммируются с помощью сумматора 800 с соответствующими символами кодового слова, считываемого из буферной памяти данных. Тем самым исправляются ошибочные символы кодового слова. Таким образом выполняется основная часть 5-го этапа процедуры декодирования.

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

Рассмотрим для примера обработку декодером k-го кодового слова, в котором произошло t+1 ошибок.

Сначала в 1-ом кадре (кадр соответствует времени поступления одного кодового слова) k-oe слово записывается в буфер данных 100 и одновременно в темпе поступления в декодер обрабатывается блоком вычисления синдромов 200 и блоком сортировки позиций символов 600.

Затем в первой половине 2-го кадра процессор Галуа 300 реализует алгоритм Берлекэмпа-Месси для вычисленного синдрома, анализирует L_2t и в начале второй половины 2-го кадра загружает коэффициенты многочленов Λ^(2t)(х) и В^(2t)(х) в блок ДПФ 400 (Низкий уровень на строке "БДПФ" фиг.9).

В течение второй половины 2-го кадра и первой половины 3-го кадра блок ДПФ 400 выполняет преобразование Фурье многочленов Λ^(2t)(x) и В^(2t)(х) k-го кодового слова (высокий уровень на строке 'БДПФ'). Кроме того, в зависимости от режима работы он вычисляет коэффициенты C_i или D_i и A_i, которые загружаются в память БППО, адресуемую с помощью таблицы перестановок L блока БСПС. Если L_2t≤t блок ДПФ 400 также вычисляет величины, обратные к корням полинома Λ^(2t)(х), и контролирует их число.

В течение второй половины 3-го кадра и первой половины 4-го кадра блок поиска позиций ошибок веса t+1 500 выполняет вычисление значений величины (или Δ=Δ_2t+1) k-го кодового слова, их подсчет и фиксацию тех их значений, которые встретились в цикле сканирования ровно t раз.

В течение второй половины 4-го кадра и первой половины 5-го кадра блок поиска позиций ошибок веса t+1 500 с помощью зафиксированного значения Δ определяет позиции t+1 ошибочных символов k-го кодового слова. Значения этих позиций корректируются с помощью таблицы L во время их пересылки в процессор Галуа.

В течение второй половины 5-го кадра процессор Галуа 300 вычисляет многочлены Ω(х) и Λ'(х) и загружает их в блок вычисления значений ошибок 700.

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

Аналогичным образом осуществляется обработка k+1, k+2 и т.д. принятых из канала кодовых слов.

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

Блок сортировки позиций символов 600

Функциональная схема блока сортировки позиций символов (БСПС) 600 приведена на фиг.2. Блок содержит: схему сравнения кодов 610; пять блоков памяти отсортированных позиций (БПОП) 620.1-620.5; два пятивходовых коммутатора 630.1, 630.2; двоичный счетчик на n 640; два двоичных счетчика на 5 650.1, 650.2; два дешифратора на 5 состояний 660.1, 660.2; пять двухвходовых коммутатора 670.1-670.5.

БСПС осуществляет сортировку позиций символов принятого из канала кодового слова в соответствии с их надежностью. Сортировка осуществляется в процессе поступления символов в декодер, при этом формируется таблица перестановок L. Таблица состоит из двух частей: по младшим адресам располагаются позиции ненадежных символов (для которых надежность меньше заданного порога), по старшим адресам располагаются позиции оставшихся символов. Сравнение надежности символа с порогом осуществляет схема сравнения кодов 610, на выходе которой формируется логическая «1», если величина надежности, подаваемая на первые входы БСПС SoftIn, будет больше значения порога «Thres».

Таблицы перестановок формируются и затем хранятся в каждом из блоков БПОП 620. Пять блоков необходимы для организации конвейерной работы декодера с учетом того, что сформированная таблица L для кодового слова будет использоваться с задержкой.

Величина задержки видна на временных диаграммах работы декодера (фиг.9). Так, для k-го кодового слова таблица перестановок формируется в 1-ом кадре, используется во 2-ой половине 2-го и 1-ой половине 3-го кадра, и еще раз - во 2-ой половине 4-го и 1-ой половине 5-го кадра.

Пять блоков БПОП 620 позволяют формировать таблицу L для символов поступающего в декодер кодового слова и одновременно использовать таблицы перестановок для обработки двух других поступивших в декодер ранее кодовых слов.

Для организации одновременного обращения к трем из пяти блоков БППО используются счетчики 640, 650.1, 650.2; дешифраторы 660.1, 660.2 и коммутаторы 630.1, 630.2, 670.1-670.5. Счетчики 640, 650.1 и дешифратор 660.1 предназначены для управления записью в БПОП при формировании таблицы перестановок. Счетчик 640 хранит позицию текущего символа, которая подается на вход данных DI всех БПОП одновременно с подачей флага надежности, формируемого схемой сравнения кодов 610, на вход S БПОП. Запись будет осуществляться в тот БПОП, на вход которого подается логический "0" (активный уровень) с выхода дешифратора 660.1.

Счетчик 650.2, дешифратор 660.2 и коммутаторы предназначены для управления чтением из БПОП при обращении к таблице перестановок. Причем коммутаторы 630.1, 630.2 предназначены для подключения выходов DO БПОП ко вторым (DOR1) или первым (DOR2) выходам блока 600 БСПС. Коммутаторы 670.1-670.5 предназначены для подключения адресных входов Adr БПОП к третьим (AdR1) или вторым (AdR2) входам БСПС. Направление передачи данных коммутаторами определяется счетчиком 650.2.

Функциональная схема БПОП 620 приведена на фиг.3. БПОП содержит: два блока памяти с произвольным доступом 621.1, 621.2; два логических элемента И-НЕ 622, 627; два двоичных счетчика 623.1, 623.2; четыре коммутатора 624.1, 624.2, 625.1, 625.2; вычитатель 626.

Память 621.1 предназначена для хранения позиций ненадежных символов кодового слова таблицы перестановок L, позиции надежных символов хранятся в памяти 621.2.

БПОП работает в двух режимах:

1) режиме записи в память позиции символа кодового слова;

2) режиме чтения из таблицы перестановок.

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

БПОП в первом режиме работает следующим образом. По активному сигналу , подаваемому на третий вход БПОП, коммутаторы 624 подают на третьи (адресные входы) блоков памяти 621 содержимое счетчиков 623, которые содержат адреса следующих незаписанных ячеек памяти. Если на второй вход БПОП подается сигнал sel=0 (для ненадежного символа), по сигналу осуществляется запись позиции символа с первых входов БПОП (DI) в память 621.1 и по завершению записи содержимое счетчика 623.1 инкрементируется. Если сигнал sel=1 (для надежного символа), осуществляется запись в память 621.2 и инкремент счетчика 623.2.

Во втором режиме работы БПОП осуществляется выдача на выходы БПОП (DO) следующей информации:

1) количества позиций ненадежных символов, хранимых в памяти 621.1 (содержимое счетчика 623.1), необходимое для определения переменной n_C в формулах (12, 13);

2) содержимого таблицы перестановок L по адресу, поданному на четвертые входы БПОП (Adr) (содержимое ячейки памяти 621.1 или 621.2).

Если старший бит входной шины Adr равен «1», то через коммутатор 625.2 на выходы БПОП (DO) подается содержимое счетчика 623.1. В противном случае на выходы через коммутаторы 625 подается содержимое одного из блоков памяти 621.

Если содержимое шины Adr будет меньше содержимого счетчика 623.1 (заем на втором выходе вычитателя 626, управляющий коммутатором 625.1, отсутствует), то на выходы БПОП будет подаваться содержимое ячейки памяти 621.1, адресуемой непосредственно содержимым шины адреса Adr. В противном случае на выходы БПОП будет подаваться содержимое ячейки памяти 621.2, адресуемой разностью содержимого шины адреса Adr и содержимого счетчика 623.1.

Блок дискретного преобразования Фурье 400

Функциональная схема блока дискретного преобразования Фурье 400 приведена на фиг.7. Блок содержит: местное устройство управления (МУУ) 410; модуль дискретного преобразования Фурье многочлена Λ^(2t)(х) 420.1; модуль дискретного преобразования Фурье многочлена B^(2t)(х) 420.2; перекрестный коммутатор 430; инвертор элементов поля Галуа 440; перемножитель двух элементов поля Галуа 450; двухвходовый коммутатор 460, умножитель на α 470; регистр-защелку 480, работающую по фронту тактового сигнала; двоичный счетчик номеров позиций принятого слова 490 с коэффициентом пересчета n.

Местное устройство управления 410 предназначено для взаимодействия с процессором Галуа 300 и управления блоком ДПФ 400. Оно также накапливает возможные позиции ошибок веса, меньшего t+1, запоминая значения i в момент равенства нулю значения многочлена Λ^(2t)(α^-i) (сигнал sel0) и подсчитывая их количество.

Двоичный счетчик 490 предназначен для формирования значения i.

Регистр 480 и умножитель на α 470 обеспечивают формирование величины A_i=αⁱ.

Блок ДПФ 400 - может работать в трех режимах.

Нулевой режим. В этом режиме блок ДПФ 400 работает, когда L_2t<t. При этом в него загружаются только значения коэффициентов полинома Λ^(2t)(х) и ищутся позиции ошибок веса, меньшего t. Значения сигналов на первых, четвертых-шестых выходах Б ДПФ (AddR1, C_i|D_i, Mskl, A_i) игнорируются.

Первый режим. В этом режиме блок ДПФ 400 работает, когда L_2t=t. В него загружаются значения коэффициентов обоих полиномов Λ^(2t)(х) и B^(2t)(x). Осуществляется поиск позиций ошибок веса t. Вычисляются коэффициенты . Для их вычисления перекрестный коммутатор 430 работает в прямом направлении, подавая на вход инвертора 440 коэффициенты Λ(α^-i). На пятом выходе БППФ значение Msk1 (исключение уравнений из системы) формируется путем подачи через коммутатор 460 сигнала со второго выхода модуля дискретного преобразования Фурье 420.1, который имеет единичный уровень, когда Λ(α^-i)=0.

Второй режим. В этом режиме блок ДПФ 400 работает, когда L_2t=t+1. В него загружаются значения коэффициентов полиномов Λ^(2t)(х) и х²·В^(2t)(х). Вычисляются коэффициенты . Для их вычисления перекрестный коммутатор 430 работает в перекрестном режиме, подавая на вход инвертора 440 значения α^-2iB(α^-i). На пятом выходе БППФ значение Msk1 формируется путем подачи через коммутатор 460 сигнала со второго выхода модуля дискретного преобразования Фурье 420.2, который имеет единичный уровень, когда В(α^-i)=0.

В каждом такте работы блока ДПФ 400 на первых выходах модуля дискретного преобразования Фурье многочлена Λ(х) 420.1 появляется значение Λ(α^-i), на первых выходах модуля дискретного преобразования Фурье многочлена В(х) 420.2 появляется значение В(α^-i) (или α^-2iB(α^-i)), на выходе регистра 480 формируется значение A_i. За время цикла работы блока ДПФ 400 i пробегает значения 0, …, n-1.

В первом и втором режимах A_i, C_i|D_i и Msk1 записываются в буферную память 550 блока поиска позиций ошибок веса t+1 500. Для формирования адресов памяти 550 при записи используется счетчик 490, значение которого подается на вход таблицы перестановок L, хранящейся в блоке сортировки позиций символов 600.

Функциональная схема модуля дискретного преобразования Фурье многочлена Λ^(2t)(х) 420.1 (модуль дискретного преобразования Фурье многочлена В^(2t)(х) 420.2 реализуется по точно такой же схеме) приведена на фиг.8.

Модуль 420 содержит блок вентилей 421, регистры-защелки, работающие по фронту тактового импульса, 422.0 - 422.t+1, сумматор элементов поля Галуа на t+2 входа 423, селектор нулевого элемента поля Галуа 424, умножители на постоянные коэффициенты в поле Галуа 425.1 - 425.t+1, блоки логических элементов ИЛИ 426.1 - 426.t+1.

Перед началом работы блока ДПФ 400 регистры 422.0 - 422.t+1 обнуляются. Затем процессор Галуа 300 с помощью местного устройства управления 410 загружает в эти регистры через блок вентилей 421 и блоки логических элементов ИЛИ 426.1 - 426.t+1 коэффициенты полинома Λ^(2t)(х) (В^(2t)(х), x²B^(2t)(x)). Сумма всех регистров 422.0-422.t+1

сразу даст значение полинома в точке х=α⁰ на выходах сумматора элементов поля Галуа 423.

Затем содержимое каждого регистра 422.k (k=1, …, t+1) соответственно умножается на α^-k с помощью умножителя на постоянные коэффициенты 425.k, где k соответствует степени неизвестной при обрабатываемом в регистре коэффициенте полинома. После этого сумма всех регистров 422.0 - 422.t+1 даст значение полинома в точке х=α^-1.

Процесс повторяется до тех пор, пока не вычислится значение полинома в точке х=α^-(n-1). Все это время селектор нулевого элемента поля 424 активизирует сигнал sel0 при обнаружении нулевого значения полинома на выходах сумматора 423.

Блок поиска позиций ошибок веса t+1 500

Для снижения аппаратной сложности желательно, чтобы блок поиска позиций ошибок веса t+1 (БППО) 500 выполнял вычисления по возможности одинаково с коэффициентами C_i в случаях, когда L_2t=t, и с коэффициентами D_i в случаях, когда L_2t=t+1. Для этого в первом случае подсчитывают значения не невязки Δ_2t+1, а обратной к ней величины .

Функциональная схема блока поиска позиций ошибок веса t+1 500 приведена на фиг.4. БППО содержит: два блока вычисления невязки Δ' (БВН) ( или Δ'=Δ_2t+1) 510.1, 510.2; два блока подсчета невязок Δ' (БПН) 520.1, 520.2; коммутатор 530; регистр-защелку 540; блок памяти коэффициентов (БПК) 550, местное устройство управления (МУУ) 560.

Блоки 510.1, 510.2 выполняют вычисления Δ' в соответствии с формулами (12) или (13) в зависимости от значения L_2t.

Блоки 520.1, 520.2 осуществляют подсчет различных значений величины Δ' в поле Галуа (w_i,l) и фиксируют ситуацию равенства t количества какого-то значения Δ'.

Определенные для этой ситуации значения Δ'', и поступают из соответствующей пары блоков 510 и 520 через коммутатор 530 на входы регистра 540 и запоминаются в нем.

Блок памяти коэффициентов 550 предназначен для временного хранения величин A_i, C_i (или D_i) и бит Msk1. Он содержит 3 секции, операции с которыми выполняются одновременно. В одну секцию величины A_i, C_i (или D_i) и биты Msk1 поступают из блока ДПФ 400, из другой секции задержанные на один кадр они считываются и поступают в блоки 510.1-510.2 для вычисления Δ', из следующей секции эти величины, задержанные еще на один кадр, считываются и используются для повторного вычисления последовательности Δ', необходимой для фиксации позиций ошибочных символов. БПК 550 может быть реализован известным образом на основе трехпортовой RAM.

Местное устройство управления 560 предназначено для взаимодействия с процессором Галуа 300 и управления блоком БППО. В том числе, оно вычисляет последовательность адресов чтения блока памяти коэффициентов 550. Оно также накапливает позиции конфигурации ошибок веса t+1, записывая в стек значения AR2 в момент равенства величин Δ' и Δ (сигнал SX_i).

Две пары блоков БВН+БПН 510 и 520 необходимы для обеспечения конвейерного режима работы блока поиска позиций ошибок. Каждая пара блоков 510 и 520 обрабатывает коэффициенты C_i (или D_i) одного кодового слова в течение двух кадров (см. фиг.9). В каждом кадре одна пара осуществляет вычисления Δ' и подсчет их значений, БВН другой пары осуществляет вычисления Δ' для фиксации позиций ошибочных символов в предыдущем кодовом слове, одновременно осуществляется очистка памяти БПН этой же пары.

На фиг.4 пара блоков 510.1+520.1 осуществляет подсчет различных значений Δ' для k-го кодового слова во второй половине 3-го кадра и первой половине 4-го. Фиксация позиций ошибочных символов для k-го слова осуществляется во второй половине 4-го кадра и первой половине 5-го с использованием блока 510.1, в это же время записывается нулями память БПН 520.1. Аналогичным образом работает пара блоков 510.2+520.2, обрабатывая t+1-ое кодовое слово со смещением на кадр.

Рассмотрим устройство и работу основных блоков БППО.

Функциональная схема блока вычисления невязок Δ' (БВН) 510 приведена на фиг.5. БВН содержит: три коммутатора с двух направлений 511.0, 511.1 и 511.2; два регистра-защелки, работающих по фронту тактового сигнала 512.1 и 512.2; два сумматора элементов поля Галуа 513.1 и 513.2; инвертор элементов поля Галуа 514; перемножитель элементов поля Галуа 515; схему сравнения кодов (на выходе логическая "1", если коды на входах равны) 516.1; селектор нулевого элемента поля Галуа 516.2; два элемента логическое И 517.1 и 517.2; элемент логическое ИЛИ-НЕ 518; D-триггер, работающий по фронту тактового сигнала 519.

БВН работает в 2-х режимах.

В первом (основном) режиме БВН вычисляет значение Δ' по формуле (12) или (13) и формирует инверсный бит маскирования для блока подсчета невязок 520.

В начале цикла сканирования по сигналу Ld (см. фиг.5), подаваемому на восьмой вход БВН, в регистр 512.1 через коммутатор 511.1 защелкивается коэффициент A'_l(i) (адрес данных чтения AR1 БПК 550 при этом равен i), в регистр 512.2 через коммутатор 511.2 защелкивается коэффициент C'_L(i) (D'_L(i)), в триггер 519 защелкивается бит маски Msk1'. В следующих тактах из БПК 550 считываются коэффициенты A'_l(j), C'_L(j) (d'_l(j)) вместе с соответствующим битом маски (адреса данных чтения БПК при этом будут пробегать значения j=i+1, …, n-1). На выходах сумматора элементов поля 513.1 формируются суммы A'_L(i)+A'_l(j) (в поле Галуа характеристики 2 вычитание совпадает со сложением). Инвертор 514 находит обратную величину полученной суммы в поле Галуа. На выходах сумматора элементов поля 513.2 формируются суммы C'_l(i)+C'_l(j) (D'_l(i)+D'_l(j)), на выходах перемножителя 515 получаются величины (или для L_2t=2t+1). С помощью бита маскирования Msk2, формируемого логическим элементом ИЛИ-НЕ 518, из подсчета убираются Δ', для которых Λ^(2t)(α^-i)=0 (или В^(2t)(α^-i)=0 для L_2t=2t+1). Кроме того, из подсчета убираются нулевые значения Δ' с помощью селектора нулевого элемента поля 516.2 и логического элемента И 517.2.

Во втором режиме определяются значения t позиций ошибочных символов (значение позиции первой ошибки определяется в местном устройстве управления 560 при обнаружении ровно t значений Δ'). Для этого повторяют цикл вычисления Δ', на котором был обнаружен набор из t одинаковых значений Δ', используя значения А''_L(i), С''_L(j) (D''_l(j), Msk1'' со вторых входов блока памяти коэффициентов 550. При этом последовательность Δ' сравнивается схемой сравнения кодов 516.1 с запомненным в регистре 540 значением Δ''. Всякий раз при сравнении сигнал SX_i принимает значение логической 1, и в этот момент времени значение AR2 принимается как значение позиции РЕ' ошибочного символа (без учета перестановки).

Блок подсчета невязок (БПН) 520 содержит (см. фиг.6): блок вентилей 521, блок памяти с произвольной выборкой 522 с защелкой выходных данных на выходе по фронту тактового сигнала, схему инкремента 523, схему сравнения кодов 524, коммутатор с двух направлений 526, регистр-защелку 527, логические элементы И 525 и 528.

В основе БПН лежит память 522, которая содержит 2^m слов (2^m - число элементов конечного поля Галуа) разрядностью log₂t. Слово памяти хранит значение счетчика соответствующего значения Δ' (w_i,l).

Блок подсчета невязок работает в двух режимах.

В первом режиме осуществляется подсчет различных значений Δ'. Поступающие на вход блока значения Δ', защелкиваются в регистр 527. Содержимое ячейки памяти 522 (счетчик w_i,l), соответствующее этому значению Δ', увеличивается на 1 с помощью схемы инкремента 523 и записывается в ту же ячейку памяти через открытый блок вентилей 521. Схема сравнения кодов 524 проверяет, не достигло ли значение счетчика t, и если достигло, то формирует сигнал обнаружения значения невязки Δ', соответствующего конфигурации ошибок веса t+1.

Уровень логического нуля на выходе элемента 528, формируемый при активном сигнале Msk2 или неактивном сигнале разрешения работы Е, блокирует инкрементирование количества Δ', находящегося на выходе памяти.

Во втором режиме работы БПН (режиме инициализации), задаваемом сигналом I на первом входе БПН, во все ячейки памяти 522 записываются нулевые слова. Адреса ячеек памяти 522 в этом режиме поступают через коммутатор 526 из местного устройства управления 560. Нулевые слова на входе памяти 522 получают с помощью блока вентилей 521.

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

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

Результаты исследования быстродействия заявляемого декодера в канале с аддитивным белым гауссовским шумом (AWGN) и модуляцией BPSK приведены на фиг.10. В качестве меры надежности символа слова PC-кода использовалось минимальное значение модулей мягких решений составляющих его бит.

Имитационным моделированием исследовались PC-коды с d=13, определенные над конечным полем GF(2⁸), n_c=30. Модель канала - BPSK, AWGN, E_b/No=7 db. На графике ξ обозначает коэффициент повышения быстродействия поиска неизвестных невязок, равный отношению n_s·n_w (n_w - число обработанных кодовых слов в процессе моделирования) к реальному числу вычислений невязок декодером при исправлении t+1 ошибок.

Кривая 1 соответствует случаю декодирования кодовых слов с t+1 ошибкой по алгоритму [3] (характеризует возможность повышения быстродействия декодера-прототипа за счет усреднения времени декодирования кодовых слов), кривая 2 - случаю управления поиском невязок информацией о надежности принятых из канала символов. Для получения значения ξ в одной точке обрабатывалось n_w=10⁷ кодовых слов. Из графика видно, что выигрыш по быстродействию при управляемом поиске составляет примерно два десятичных порядка.

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

Источники информации

1. Патент 6631172 США. МПК⁷ H03D 1/00. Efficient List Decoding Of Reed-Solomon Codes For Message Recovery In The Presence Of High Noise Levels. / Mohammad Amin Shokrollahi, Vadim Olshevsky - заявлено 01.05.2000 N09/563602; опубл. 07.10.2003.

2. Патент 6634007 США. МПК⁷ Н03М 13/00. Algebraic Soft-Decision Decoding of Reed-Solomon codes. / Ralf Koetter, Alexander Vardy - заявлено 23.01.2000 N09/602914; опубл. 14.10.2003.

3. Egorov S., Markarian G., Pickavance K. A Modified Blahut Algorithm for Decoding Reed-Solomon Codes Beyond Half the Minimum Distance // IEEE Trans. on Commun., vol.52, no.12, December. 2004, pp.2052-2056.

4. Егоров С.И. Коррекция ошибок в информационных каналах периферийных устройств ЭВМ. Монография. Курск: Курск, гос. техн. ун-т, 2008. - 252 с.

5. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. - М.: Мир, 1986. - 576 с.

Изобретение относится к системам телекоммуникаций и вычислительной технике и может найти применение в устройствах приема информации из канала передачи или воспроизведения информации с высоким уровнем ошибок. Техническим результатом является повышение быстродействия исправления ошибок за границей половины минимального расстояния путем использования информации о надежности принятых из канала символов. Устройство содержит буферную память данных, блок вычисления синдромов, процессор Галуа, блок дискретного преобразования Фурье, блок поиска позиций ошибок веса t+1, блок сортировки позиций символов, блок вычисления значений ошибок, сумматор элементов поля Галуа. 5 з.п. ф-лы, 10 ил.

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

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

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

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

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

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