Устройство декодирования кодов рида-соломона

Устройство декодирования кодов рида-соломона

Иллюстрации

Показать все

Реферат

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

В настоящее время на практике применяются устройства декодирования кодов Рида-Соломона (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.