Устройство мажоритарного декодирования кода рида-соломона по k-элементным участкам кодовой комбинации с порогом определения неисправляемой ошибки

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

 

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

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

Известно устройство декодирования кодов Рида-Соломона, позволяющее исправить одну ошибку за границей гарантированно исправляемой кратности ошибок [см. 1. Патент на изобретение РФ №2441318, МПК Н03М 13/45, опубл. 27.01.2012], которое содержит буферную память данных, блок вычисления синдромов, процессор Галуа, блок дискретного преобразования Фурье, блок поиска позиций ошибок, блок вычисления значений ошибок, первый сумматор элементов поля Галуа, причем входы буферной памяти данных и входы блока вычисления синдромов являются входами символов данных устройства декодирования кодов Рида-Соломона, выходы буферной памяти данных соединены с первыми входами первого сумматора элементов поля Галуа, выходы блока вычисления синдромов соединены с первыми входами процессора Галуа, первые выходы процессора Галуа соединены с первыми входами блока дискретного преобразования Фурье, вторые выходы процессора Галуа соединены со вторыми входами блока дискретного преобразования Фурье, третьи выходы процессора Галуа соединены с третьими входами блока дискретного преобразования Фурье, четвертые выходы процессора Галуа соединены с четвертыми входами блока поиска позиций ошибок, пятые выходы процессора Галуа соединены с первыми входами блока вычисления значений ошибок, шестые выходы процессора Галуа соединены со вторыми входами блока вычисления значений ошибок, седьмые выходы процессора Галуа соединены с третьими входами блока вычисления значений ошибок, вторые выходы блока дискретного преобразования Фурье соединены с третьими входами процессора Галуа, третьи выходы блока дискретного преобразования Фурье соединены с четвертыми входами процессора Галуа, четвертые выходы блока дискретного преобразования Фурье соединены с первыми входами блока поиска позиций ошибок, пятый выход блока дискретного преобразования Фурье соединен со вторым входом блока поиска позиций ошибок, шестые выходы блока дискретного преобразования Фурье соединены с третьими входами блока поиска позиций ошибок, первые выходы блока поиска позиций ошибок соединены с пятыми входами процессора Галуа, вторые выходы блока поиска позиций ошибок соединены с шестыми входами процессора Галуа, третьи выходы блока поиска позиций ошибок соединены с седьмыми входами процессора Галуа, четвертые выходы блока поиска позиций ошибок соединены с восьмыми входами процессора Галуа, выходы блока вычисления значений ошибок соединены со вторыми входами первого сумматора элементов поля Галуа, выходы первого сумматора элементов поля Галуа являются выходами данных устройства декодирования кодов Рида-Соломона, отличающееся тем, что в устройство введен блок сортировки позиций символов, причем первые входы блока сортировки позиций символов являются входами оценок надежности символов данных устройства декодирования кодов Рида-Соломона, пятые выходы блока поиска позиций ошибок соединены со вторыми входами блока сортировки позиций символов, первые выходы блока дискретного преобразования Фурье соединены с третьими входами блока сортировки позиций символов, первые выходы блока сортировки позиций символов соединены со вторыми входами процессора Галуа, вторые выходы блока сортировки позиций символов соединены с пятыми входами блока поиска позиций ошибок.

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

Известно также устройство декодирования систематических (n,k)-кодов Рида-Соломона [см. 2. Патент США №2013/0198583 А1, МПК Н03М 13/15, опубл. 01.08.2013], обеспечивающее быструю обработку кодовой комбинации, основанную на определении информационной комбинации на основе k-элементной последовательности принятой кодовой комбинации. Декодер, используемый в данном устройстве, содержит блок обработки входной последовательности, обеспечивающий выделение и распаковку k элементов кодовой комбинации из поступаемых на вход n элементов кодовой комбинации, где n - полная длина кодовой комбинации, а k - общее число информационных элементов в кодовой комбинации, блок вычисления информационных элементов, основанный на использовании быстрого преобразования Уолша-Адамара и быстрого преобразования Фурье, блок обработки информационных элементов и блок восстановления информационных элементов. При этом входы блока обработки входной последовательности являются входами данных устройства декодирования кодов Рида-Соломона, выходы блока обработки входной последовательности подключены к соответствующим входам блока вычисления k информационных элементов, а его выходы связаны с соответствующими входами блока обработки информационных элементов, выходы которого подключены к соответствующим входам блока восстановления информационных элементов, выходы которого являются выходами данных устройства декодирования кодов Рида-Соломона.

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

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

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

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

При этом блок вычисления информационных элементов может содержать k блоков умножения на коэффициенты двойственного базиса, вычисленные по формуле . (см. 3. Когновицкий О.С. Двойственный базис и его применение в телекоммуникациях. СПб.: Линк, 2009, 423 с.), где k - количество информационных элементов в кодовой комбинации кода Рида-Соломона, ε_i - элементы левого степенного базиса поля Галуа, p_k - коэффициенты порождающего полинома Р(х), Р'(х) - производная порождающего полинома Р(х), блок суммирования в поле Галуа и блок умножения на коэффициенты позиции k-элементной комбинации, вычисляемые по формуле , в которой i - положение первого элемента k-элементного участка относительно начала кодовой комбинации (см. 3. Когновицкий О.С. Двойственный базис и его применение в телекоммуникациях. СПб.: Линк, 2009, 423 с.), при этом k-линейные входы блоков умножения на коэффициенты двойственного базиса являются входами блока вычисления информационных элементов, а их k-линейные выходы связаны с соответствующими входами блока суммирования в поле Галуа, k-линейный выход которого связан с входом блока умножения на коэффициенты позиции k-элементной комбинации, выход которого является выходом блока вычисления информационных элементов.

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

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

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

Введенные отличия изменяют механизм вычисления информационных элементов и принцип обработки вычисленных информационных элементов.

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

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

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

Предлагаемое устройство поясняется чертежами, где на фиг. 1 приведена структурная схема устройства мажоритарного декодирования кода Рида-Соломона по k-элементным участкам кодовой комбинации, на фиг. 2 показана структура блока вычисления информационных элементов, на фиг. 3 приведена структура блока хранения вычисленных элементов, на фиг. 4 - схема блока памяти, входящего в блок хранения вычисленных элементов, на фиг. 5 - структура блока принятия решения, а на фиг. 6 - алгоритм работы устройства.

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

Блок 2 вычисления информационных элементов, показанный на фиг. 2, содержит k блоков 2.1.l-2.1.k умножения на коэффициенты двойственного базиса, блок 2.2 суммирования в поле Галуа, блок 2.3 умножения на коэффициенты позиции k-элементной комбинации, при этом k-линейные входы блоков 2.1.l-2.1.k умножения на коэффициенты двойственного базиса являются входами блока 2 вычисления информационных элементов, а их k-линейные выходы связаны с соответствующими входами блока 2.2 суммирования в поле Галуа, k-линейный выход которого связан с входом блока 2.3 умножения на коэффициенты позиции k-элементной комбинации, выход которого является выходом блока 2 вычисления информационных элементов.

Блок 3 хранения вычисленных элементов (фиг. 3) содержит n идентичных блоков памяти 3.1.l-3.1.n, входы которых являются входами блока 3 хранения вычисленных элементов.

Каждый блок 3.1.l-3.1.n памяти (фиг. 4), входящий в блок 3 хранения вычисленных элементов, содержит управляющее устройство 3.1.2, регистр 3.1.3 памяти, компаратор 3.1.4 и счетчик 3.1.5, при этом входы управляющего устройства 3.1.2 являются входами блока 3.1.1 памяти, а его соответствующие выходы связаны с входами регистра 3.1.3 памяти, счетчика 3.1.5, компаратора 3.1.4, причем соответствующие выходы регистра 3.1.3 памяти связаны с соответствующими входами компаратора 3.1.4 и являются выходами данных соответствующего блока памяти 3.1.1, а первый выход компаратора 3.1.4 соединен с соответствующим входом счетчика 3.1.5, выходы данных и выход счетчика 3.1.5 каждого блока памяти 3.1.1 являются выходами блока 3 хранения вычисленных элементов, а второй выход компаратора 3.1.4 является выходом включения следующего блока памяти.

Блок 4 принятия решения (фиг. 5) содержит блок 4.1 поиска максимального значения счетчиков, блок 4.2 вывода результата декодирования, блок 4.3 вычисления разности между значениями счетчиков и блок 4.4 сравнения с порогом. Соответствующие входы блока 4.1 поиска максимального значения счетчиков и соответствующие вторые входы блока 4.3 вычисления разности между значениями счетчиков служат для подключения выходов счетчиков 3.1.5 блоков памяти 3.1.l-3.1.n блока 3 хранения вычисленных элементов. Первый выход блока 4.1 поиска максимального значения счетчиков связан со вторым входом блока 4.2 вывода результата декодирования. Второй выход блока 4.1 поиска максимального значения счетчиков связан с первым входом блока 4.3 вычисления разности между значениями счетчиков. Выходы блока 4.3 вычисления разности между значениями счетчиков связаны с соответствующими первыми входами блока 4.4 сравнения с порогом, второй вход которого является входом значения порога. Первые входы блока 4.2 вывода результата декодирования служат для подключения соответствующих k-линейных выходов данных блоков памяти 3.1.l-3.1.n блока 3 хранения вычисленных элементов. Выход блока 4.2 вывода результата декодирования является выходом результата декодирования устройства 4 принятия решения. Выход блока 4.4 сравнения с порогом является выходом признака ошибки декодирования устройства 4 принятия решения.

Рассмотрим работу предлагаемого устройства с использованием фиг. 1, 2, 3, 4, 5.

Входная кодовая комбинация длины n поступает в блок 1 обработки входной последовательности, в котором по мере приема кодовой комбинации из нее выделяются k-элементные комбинации, которые поступают на вход блока 2 вычисления информационных элементов. В блоке 2 вычисления информационных элементов k-элементная комбинация передается на входы блоков 2.1.l-2.1.k умножения на коэффициенты двойственного базиса, хранящиеся в узлах памяти этих блоков, полученные результаты складываются в блоке 2.2 суммирования в поле Галуа, результат поступает на вход блока 2.3 умножения на коэффициенты позиции k-элементной комбинации, также хранящиеся в узле памяти этого блока. Полученные в результате k информационных элементов поступают на входы соответствующих блоков 3.1.l-3.1.n памяти блоков 3 хранения вычисленных элементов. При первом появлении сигналов на входе данных блоков 3.1.l-3.1.n памяти, при условии, что есть сигнал на их входах включения, управляющее устройство 3.1.2 передает данные с входа данных в регистр 3.1.3 памяти и увеличивает значение счетчика 3.1.5 на единицу. При повторном появлении сигналов на входе данных управляющее устройство 3.1.2 передает их на второй вход компаратора 3.1.4, где эти данные сравниваются с содержимым регистра 3.1.3 памяти. В случае равенства значение счетчика 3.1.5 увеличивается на единицу по сигналу с первого выхода компаратора 3.1.4. В случае неравенства подается сигнал со второго выхода компаратора 3.1.4 на выход включения следующего блока памяти. Выходы регистра 3.1.3 памяти являются выходами данных блока памяти. Они подключены к соответствующим входам блока 4.2 вывода результата декодирования в блоке 4 принятия решения. Выходы счетчиков 3.1.5 блоков 3.1.l-3.1.n памяти поступают на соответствующие входы блока 4.1 поиска максимального значения счетчиков в блоке 4 принятия решения и соответствующие входы блока 4.3 сравнения. Путем последовательного сравнения в блоке 4.1 поиска максимального значения счетчиков выбирается вход от счетчика с максимальным значением. Номер этого входа передается с первого выхода блока 4.1 поиска максимального значения счетчиков на второй вход блока 4.2 вывода результата декодирования, а значение со входа счетчика с максимальным значением передается на первый вход блока 4.3 вычисления разности между значениями счетчиков. Соответствующий номеру входа с максимальным значением счетчика вход блока 4.2 вывода результата коммутируется с выходом информационных элементов. При этом, если это максимальное значение счетчика равно (n/2+1) или более, результат считается гарантированно верным. Согласно полученному на входе 1 блока 4.3 вычисления разности между значениями счетчиков значению счетчика с максимальным значением в блоке 4.3 сравнения проводится нахождение разности значений между счетчиком с максимальным значением и всеми остальными счетчиками. Вычисленные разности передаются с выхода блока 4.3 вычисления разности между значениями счетчиков на первые входы блока 4.4 сравнения с порогом, где производится их сравнение с поданным на вход 2 блока 4.4 сравнения с порогом значения порога. В случае обнаружения разности со значением, меньшим либо равным порогу, на выход блока 4.4 сравнения с порогом выводится сигнал об ошибке декодирования.

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

Блок 1 обработки входной последовательности может быть построен в виде циклического регистра сдвига из n ячеек памяти, например, на ПЛИС или логических ИМС типа К155ИР1 (SN7495) (см. 4. Интегральные микросхемы: Справочник / Под ред. Б.Ф. Тарабрина. - М.: Радио и связь, 1983).

Блок 2.1 умножения на коэффициенты двойственного базиса символов может быть построен на ПЛИС или логических ИМС типа К155ЛИ1 (SN7408) и К155ЛП5 (SN7486), а также микросхеме ППЗУ, например, типа 2716.

Блок 2.2 суммирования в поле Галуа может быть построен на ПЛИС или логических ИМС типа К155ЛП 5 (SN7486).

Блок 2.3 умножения на коэффициенты позиции k-элементной комбинации может быть построен на ПЛИС или логических ИМС типа К155ЛИ1 (SN7408) и К155ЛП5 (SN7486), а также микросхеме ППЗУ, например, типа 2716.

В каждом блоке памяти 3.1 регистр 3.1.3 памяти может быть построен на ПЛИС или логических ИМС типа К155ИР1 (SN7495), компаратор 3.1.4 может быть построен на ПЛИС или логических ИМС типа К561ИП2 (МС14585А), счетчик 3.1.5 может быть построен на ПЛИС или логических ИМС типа К155ИЕ2 (SN7490).

В блоке 4 принятия решения блок 4.1 поиска максимального значения счетчиков может быть построен на цепочке цифровых компараторов, например, на логических ИМС типа К561ИП2 (МС 14585А) и ключах, например, на логических ИМС типа К176КТ1.

Блок 4.2 вывода результата декодирования может быть построен на демультиплексоре, например, на логических ИМС типа К561КП2 и ключах, например, на логических ИМС типа К176КТ1.

Блок 4.3 вычисления разности между значениями счетчиков может быть построен на мультиплексоре, например, на логических ИМС типа К561КП2, демультиплексоре, например, на логических ИМС типа К561КП2, и цепочке вычитателей, например, на логических ИМС типа 74F385.

Блок 4.4 сравнения с порогом может быть построен на цепочке цифровых компараторов, например, на логических ИМС типа К561ИП2 (МС 14585А).

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

2. Устройство по п. 1, отличающееся тем, что блок вычисления информационных элементов содержит k блоков умножения на коэффициенты двойственного базиса, вычисленные по формуле , где k - количество информационных элементов в кодовой комбинации кода Рида-Соломона, ε_i - элементы левого степенного базиса поля Галуа, p_k - коэффициенты порождающего полинома P(x), P'(x) - производная порождающего полинома P(x), блок суммирования в поле Галуа и блок умножения на коэффициенты позиции k-элементной комбинации, вычисляемые по формуле , в которой i - положение первого элемента k-элементного участка относительно начала кодовой комбинации, при этом k-линейные входы блоков умножения на коэффициенты двойственного базиса являются входами блока вычисления информационных элементов, а их k-линейные выходы связаны с соответствующими входами блока суммирования в поле Галуа, k-линейный выход которого связан с входом блока умножения на коэффициенты позиции k-элементной комбинации, выход которого является выходом блока вычисления информационных элементов.

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

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

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