Устройство мажоритарного декодирования кода Рида-Соломона по k-элементным участкам кодовой комбинации Российский патент 2017 года по МПК H03M13/15 H03M13/43 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предлагаемое устройство поясняется чертежами, где на фиг. 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.1-2.1.k умножения на коэффициенты двойственного базиса, блок 2.2 суммирования в поле Галуа, блок 2.3 умножения на коэффициенты позиции k-элементной комбинации, при этом k-линейные входы блоков 2.1.1-2.1.k умножения на коэффициенты двойственного базиса являются входами блока 2 вычисления информационных элементов, а их k-линейные выходы связаны с соответствующими входами блока 2.2 суммирования в поле Галуа, k-линейный выход которого связан с входом блока 2.3 умножения на коэффициенты позиции k-элементной комбинации, выход которого является выходом блока 2 вычисления информационных элементов.

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

Каждый блок 3.1.1-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 сравнения. Выходы счетчиков 3.1.5 блоков памяти 3.1.1-3.1.n блока 3 хранения вычисленных элементов связаны со входами блока 4.1 поиска максимального значения и вторыми входами блока 4.3 сравнения. Выход блока 4.1 поиска максимального значения связан со вторым входом блока 4.2 вывода результата декодирования и первым входом блока 4.3 сравнения, k-линейные выходы данных блоков памяти 3.1.1-3.1.n блока 3 хранения вычисленных элементов связаны с первыми входами блока 4.2 вывода результата декодирования. Выход блока 4.2 вывода результата декодирования является выходом результата декодирования устройства 4 принятия решения. Выход блока 4.3 сравнения является выходом признака ошибки декодирования устройства 4 принятия решения.

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

Входная кодовая комбинация длины n поступает в блок 1 обработки входной последовательности, в котором по мере приема кодовой комбинации из нее выделяются k-элементные комбинации, которые поступают на вход блока 2 вычисления информационных элементов. В блоке 2 вычисления информационных элементов k-элементная комбинация передается на входы блоков 2.1.1-2.1.k умножения на коэффициенты двойственного базиса, хранящиеся в узлах памяти этих блоков, полученные результаты складываются в блоке 2.2 суммирования в поле Галуа, результат поступает на вход блока 2.3 умножения на коэффициенты позиции k-элементной комбинации, также хранящиеся в узле памяти этого блока. Полученные в результате k информационных элементов поступают на входы соответствующих блоков 3.1.1 - 3.1.n памяти блоков 3 хранения вычисленных элементов. При первом появлении сигналов на входе данных блоков 3.1.1-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.1-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 сравнения проводится проверка наличия другого счетчика с таким же значением. В случае обнаружения такого счетчика на соответствующий выход выводится сигнал об ошибке декодирования.

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

Блок 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 и цепочке цифровых компараторов, например, на логических ИМС типа К561ИП2 (МС 14585А).

ПРИЛОЖЕНИЕ к изобретению "Устройство мажоритарного декодирования кода Рида-Соломона по k-элементным участкам кодовой комбинации"

Как подробно изложено в [1], эквивалентные (двойственные) коды Рида-Соломона над полем GF(2^m) могут быть построены с помощью порождающего поле многочлена G(x) m-й степени, корнем которого будет в общем случае первообразный элемент ε ∈ GF(2^m). Для построения эквивалентного циклического кода Рида-Соломона, в дальнейшем РСЭ, выберем образующий многочлен , который будет являться характеристическим многочленом

порождающим возвратные рекуррентные последовательности с периодом n=2^m-1 и элементами, принадлежащими расширенному полю GF(2^m).

В соответствии с видом характеристического многочлена P(x), возвратная последовательность {S¹}, при p₀=1, будет удовлетворять рекуррентному уравнению:

где i≥k и, кроме того, все индексы i, i-1, … приводятся по модулю 2^m-1.

С другой стороны, произвольный элемент возвратной последовательности, как известно, может быть выражен через корни ε₁, ε₂, …, s_k характеристического многочлена P(x) и соответствующие корням элементы поля A, B, …, C как

Сами же элементы A, B, …, C могут быть определены, как это показано в [1] для кодов с разложимым характеристическим многочленом, по любому k-элементному безошибочному участку возвратной последовательности {S} в соответствии с выражениями:

Постоянные коэффициенты α_i, β_i, …, γ_i i=1, 2, …, k, зависят от характеристического многочлена Р(х) и определяются по полученной в [1] формуле (5) через корни ε_i и коэффициенты p_j многочлена P(x), а именно коэффициенты α_i для корня ε₁, β_i - для корня ε₂ и т.д., коэффициенты γ_i - для корня ε_k:

По такому же выражению находятся и коэффициенты β_i и γ_i соответственно для корней ε₂ и ε_m.

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

В случае систематического циклического кода РСЭ информационными элементами кода (n, k) будут начальные k элементов последовательности {S}, т.е. S₀S₁…S_k-1. Остальные избыточные элементы кодовой комбинации как рекурсивной последовательности будут находиться по рекуррентной формуле (2). Кодирующее устройство такого систематического кода реализуется довольно просто в соответствии с блок-схемой, представленной на фиг. 7a.

Другой вариант кодирующего устройства для несистематического циклического кода РСЭ реализуется в соответствии с выражением (3). Блок-схема такого кодирующего устройства представлена на фиг. 7б. Информационные элементы А, В, …, С, записанные как исходные в w-разрядные ячейки памяти с обратной связью, порождают на выходе последовательность {S}.

Выбор варианта построения кодирующего устройства следует произвести после анализа сложности реализации декодирующего устройства для обоих вариантов кода. Однако даже без подробного анализа процессов декодирования кодов РСЭ очевидно, что реализация декодирования несистематического кода более проста, чем систематического. Действительно, в результате декодирования систематического кода РСЭ по принятой комбинации сначала определяются элементы А, В, …, С по формуле (4), а затем, в соответствии с (3), находятся информационные элементы S₀, S₁, …, S_k-1. При декодировании несистематического кода РСЭ достаточно определить в соответствии с (4) только элементы А, В, ..., С, которые и являются информационными элементами.

Таким образом, следует рекомендовать применение несистематического кода РСЭ как более простого по реализации.

Рассмотрим простой пример несистематического кода Рида-Соломона, комбинации которого будут рекурсивными последовательностями.

Пример 1. Построим циклический несистематический код Рида-Соломона (n, k)=(7, 3) с образующим код многочленом P(x)=(x+1)(x+ε)(x+ε²), который порождает рекурсивную последовательность над расширенным полем GF(2³), m=3.

Пусть полином, образующий поле, имеет вид G(x)=1+x+x³, корнем которого будет первообразный элемент поля ε. После перемножения сомножителей полином P(x) будет иметь следующий вид:

Учитывая, что мы рассматриваем несистематический код РСЭ, выберем в качестве информационных элементов произвольные элементы поля GF(2³), например A=ε⁵; B=ε⁴; C=0. Эти элементы, в соответствии с (3), формируют следующую рекурсивную последовательность с периодом (2³-1)=7:

{S}=(S₀S₁S₂S₃S₄S₅S₆)=(10εε⁴ε⁶ε³ε²).

При этом корнями многочлена P(x) будут элементы, равные ε₁=1; ε₂=ε; ε₃=ε².

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

Можно проверить, что полученная на выходе последовательность {S} будет удовлетворять рекурсивному уравнению, соответствующему характеристическому многочлену Р(х) (6), т.е.

Для сравнения приведем схему систематического рекурсивного кодирующего устройства, соответствующего уравнению (7) и порождающего ту же кодовую последовательность (рис. 9).

Как видно из фиг. 9, схема кодирующего устройства систематического кода (7, 3) отличается тем, что в ячейки регистра в качестве исходных данных должны быть записаны элементы 1, 0 и ε, которые в данном варианте и будут являться информационными элементами выходной кодовой комбинации.

Кроме того, из сравнения обоих вариантов видно, что вариант КУ систематического кода (7, 3) имеет более сложную реализацию.

Наконец, приведем схему кодирующего устройства классического кода Рида-Соломона (7, 3) над полем GF(2³) с проверочным многочленом , где ε - первообразный корень образующего поле многочлена G(x)=1+x+x³.

Схема кодирующего устройства, реализующего деление многочлена x^n-kf(x)=x⁴f(x), где f(x) - многочлен исходных информационных элементов, на проверочный многочлен Q(x) и получение остатка от деления R(x), представлена на фиг. 10.

Легко проверить, что после подачи на вход исходной комбинации f(x)=ε+x² в ячейках регистра деления будет содержаться остаток:

R(x)=r₀+r₁x+r₂x²+r₃x³=ε²+ε³x+ε⁶x²+ε⁴ε³.

Таким образом, на выходе кодирующего устройства будет сформирована такая же кодовая комбинация: 10εε⁴ε⁶ε³ε².

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

Задачей декодирования кода РСЭ на основе двойственного базиса является определение информационных элементов А, В и С по k-элементным участкам принятой последовательности в соответствии с выражениями (4). Для этого по формуле (5) предварительно определим постоянные коэффициенты α_i, β_i и γ_i, i=1, 2, 3, соответственно для различных корней ε₁=1, ε₂=ε и ε₃=ε² характеристического многочлена:

α₁=ε; α₂=ε²; α₃=ε⁵;

β₁=ε²; β₂=ε⁶; β₃=1;

γ₁=ε⁵; γ₂=1; γ₃=ε⁴.

Теперь покажем, что по любому безошибочному k-элементному участку последовательности {S} могут быть определены элементы А, В и С, что и позволяет организовать мажоритарное декодирование.

Пусть был выделен участок (S₁S₅S₆)=(s⁶s³s²), т.е. i=4. Тогда, в соответствии с (4), имеем:

Возьмем другой участок (S₆S₇S₈)=(S₆S₀S₁)=(ε²10) замкнутой в кольцо последовательности {S}, т.е. i=6, и так же вычислим элементы А, В и С:

A=(α₁S₆+α₂S₀+α₃S₁)= ε⋅ε²+ε²⋅1=ε⁵;

В=ε^-6(β₁S₆+β₂S₀+β₃S₁)= ε^-6(ε²⋅ε³+ε⁶⋅1)=ε⁴;

C=ε^-12(γ₁S₆+γ₂S₀+γ₃S₁)= ε^-5(ε⁵⋅ε²+1)=0.

Как видно, получены те же элементы А, В и С, что и позволяет организовать мажоритарное декодирование по k-элементным участкам.

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

Литература

1. Патент на изобретение РФ №2441318, МПК H03M 13/45, опубл. 27.01.2012.

2. Патент США №2013/0198583 A1, МПК H03M 13/15, опубл. 01.08.2013.

3. Когновицкий О.С. Двойственный базис и его применение в телекоммуникациях. СПб.: Линк, 2009. 423 с.

4. Интегральные микросхемы: Справочник / Под ред. Б.Ф. Тарабрина. - М.: Радио и связь, 1983.

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

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

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

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

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

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

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