Декодирующее устройство кода рида - соломона

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

Полезная модель относится к области техники связи и может быть использована для декодирования кода Рида - Соломона в системах передачи цифровой информации.

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

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

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

входом блока вычисления локаторов ошибок и входом блока вычисления значения ошибок, выходы которых подключены к входам блока коррекции ошибок, третий вход которого соединен с выходом буферного накопителя, выход блока коррекции ошибок является выходом декодирующего устройства (Муттер В.М. Основы помехоустойчивой телепередачи информации. Л. Энергоатомиздат, 1990, стр.242).

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

Наиболее близким к предлагаемому устройству является декодирующее устройство кода Рида - Соломона (прототип), содержащее входной блок, буферный накопитель, блок вычисления синдрома, генератор элементов поля Галуа, блок вычисления многочлена принятых символов, блок решения ключевого уравнения и блок вычисления локаторов ошибок, причем входной блок подключен к информационному входу декодирующего устройства, первый выход входного блока соединен с входом буферного накопителя, второй выход входного блока соединен с входом блока вычисления локаторов принятых символов, выход которого соединен с входом блока вычисления синдрома, выход блока вычисления синдрома является входом блока решения ключевого уравнения, выход блока решения ключевого уравнения соединен с входом блока вычисления локаторов ошибок. (Авторское свидетельство СССР №1309317, кл. 4 Н 03 М 13/00, опубл. 1987).

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

что не контролируется и приводит к ошибочному декодированию информации.

Цель полезной модели - повышение защиты от ошибочного декодирования принятой информации за счет контроля значений локаторов ошибок в блоке восстановления информации и в дешифраторе ошибочного декодирования.

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

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

На чертеже приведена структурная схема предлагаемого устройства.

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

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

Предлагаемое устройство работает следующим образом.

На вход декодирующего устройства кода Рида - Соломона поступают т разрядные символы кода, принадлежащие полю Галуа GF(2 ^m). Общее количество символов кода Рида - Соломона, поступающее на вход декодирующего устройства, равно

k1=k+2t,

где k - информационная длина кода Рида - Соломона,

t - количество ошибок, исправляемых кодом (t3).

Входной блок 1, на который поступают эти символы, передает нестертые символы на входы буферного накопителя 3 и блока вычисления обратного преобразования Фурье 4. Кроме того, входной блок 1 передает номера принятых символов (локаторы) на вход блока вычисления многочлена 6 принятых символов. Номера принятых символов считаются по порядку с начала кода Рида - Соломона и до его конца.

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

Код Рида - Соломона состоит из символов, полученных в результате прямого преобразования Фурье исходной информации. При декодировании кода Рида - Соломона вычисляют обратное преобразование Фурье символов кода Рида - Соломона. Обратное преобразование Фурье осуществляют в блоке вычисления обратного преобразования Фурье 4. Для вычисления обратного преобразования Фурье используют символы кода Рида - Соломона r _i с выхода входного блока 1 и элементы поля Галуа d _i с выхода генератора элементов 2 поля Галуа.

Генератор элементов 2 поля Галуа представляет собой последовательный m разрядный сдвиговый регистр с обратными связями.

Вычисления обратного преобразования Фурье выполняют по рекуррентным формулам:

где a_i - символы обратного преобразования Фурье,

r_i, r _j - символы кода Рида - Соломона,

d _i, d_j - элементы поля Галуа,

i, j - переменные циклов.

Пример реализации обратного преобразования Фурье описан в источнике (Шабанов В.К. К оценке достижимого быстродействия декодирующих устройств кодов PC с исправлением стираний. Техника средств связи, сер. ТПС, 1983, вып.7, стр.27).

В блок вычисления многочлена 6 принятых символов с выхода входного блока 1 поступают локаторы принятых символов кода Рида - Соломона. В блоке вычисления многочлена 6 принятых символов вычисляют многочлен с(х) принятых символов по формуле:

где j(q) - локатор q-ого принятого символа,

- примитивный элемент поля Галуа.

В рекуррентной форме записи вычисления представляют в виде

где с_i - коэффициенты многочлена с(х).

Пример реализации устройства для вычисления многочлена локаторов принятых символов приведен в источнике (Авторское свидетельство СССР №1481902, кл. 4 Н 03 М 13/02, опубл. 1989).

Символы a_i i=0...k₁ -1 обратного преобразования Фурье с выхода блока вычисления обратного преобразования Фурье 4 поступают на вход блока вычисления синдрома 5, на другой вход которого поступают коэффициенты c _i i=0...k₁ многочлена принятых символов с выхода блока вычисления многочлена 6 принятых символов. В блоке вычисления синдрома 5 получают многочлен синдрома s(x). Многочлен синдрома s(x) вычисляют как отношение многочлена а(х), коэффициентами которого являются символы a_i i=0...k-1 обратного преобразования Фурье, и многочлена принятых символов с(х):

s(x)=а(х)/с(х).

Коэффициенты многочлена синдрома s, вычисляют по рекуррентным формулам:

В предлагаемом устройстве декодирование кода Рида - Соломона осуществляют с исправлением не более трех ошибок. Тройные ошибки в коде Рида - Соломона исправляют путем решения ключевого уравнения для коэффициентов многочлена локаторов ошибок. Коэффициенты многочлена локаторов ошибок _i и коэффициенты многочлена синдрома s_i связаны между собой ключевым уравнением (системой линейных уравнений), которое записывают в виде:

Коэффициенты многочлена локаторов ошибок _i, через компоненты синдрома выражают в форме

где , _i - определители системы линейных уравнений.

Для случая трех ошибок t=3, используя последнюю формулу, коэффициенты многочлена локаторов ошибок запишем в виде:

где

На вход блока решения ключевого уравнения 7 с выхода блока вычисления синдрома 5 поступают коэффициенты синдрома s ₀...s₅. Блок решения ключевого уравнения 7 вычисляет коэффициенты многочлена локаторов ошибок в соответствии с формулами (4).

Далее коэффициенты многочлена локаторов ошибок с выхода блока решения ключевого уравнения 7 поступают на вход блока вычисления локаторов ошибок 9.

Локаторы ошибок являются корнями многочлена локаторов ошибок

x ³+₁x²+₂х+₃=0.

С помощью подстановки

последнее уравнение приведем к виду

где коэффициент

Блок вычисления локаторов ошибок 9 сначала вычисляет коэффициент r по формуле (7), определяет корни уравнения (6), а затем вычисляет локаторы ошибок по формуле (5).

В качестве примера реализации блока вычисления локаторов ошибок 9 рассмотрим реализацию блока с использованием постоянного запоминающего устройства (ПЗУ).

Решения уравнения (6) в поле Галуа GF(2 ^m) определяют с помощью заранее запрограммированного ПЗУ. Адресным входом такого ПЗУ является значение коэффициента r, имеющего m разрядов, а содержимым или выходом ПЗУ - корни уравнения (6). Уравнение (6) для некоторых значений коэффициента r может не иметь решений в поле Галуа GF(2^m), в этом случае в ПЗУ по адресу, который определяется значением коэффициента r, при программировании ПЗУ, записывают запрещенные комбинации. Запрещенными комбинациями могут быть двоичные комбинации, значения которых не принадлежат полю Галуа GF(2^m ), например, двоичные комбинации, значение которых больше числа 2^m-1. Наличие запрещенной комбинации на выходе ПЗУ будет означать, что в коде Рида - Соломона произошла неисправимая комбинация ошибок и следует отказаться от декодирования кода Рида - Соломона. В этом случае блок вычисления локаторов ошибок 9, путем дешифрации этой запрещенной комбинации, формирует сигнал отказа от декодирования, который далее поступает на вход схемы ИЛИ 12.

В том случае, если уравнение (6) имеет решения в поле Галуа GF(2^m), блок вычисления локаторов ошибок 9 вычисляет локаторы ошибок по формуле (5). Далее локаторы ошибок, определяющие местоположение ошибок в коде Рида - Соломона, поступают с выхода блока вычисления локаторов ошибок 9 на управляющий вход коммутатора 8.

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

Далее с выхода коммутатора 8 символы кода Рида - Соломона поступают на вход блока восстановления информации 10. Из общего количества k+2t символов кода Рида - Соломона коммутатор 8 пропускает на вход блока восстановления информации 10 только k+t символов. Из этих символов для восстановления исходной информации кода Рида - Соломона достаточно лишь k символов, a t символов являются избыточными символами. Блок восстановления информации 10 осуществляет обратное преобразование Фурье k+t символов. Символы кода Рида - Соломона, по определению кода, представляют собой прямое преобразование Фурье исходных информационных символов, дополненных нулевыми символами до блоковой длины кода. Поэтому, при обратном преобразовании Фурье будут получены k+t символов, из которых, при правильном декодировании информации, k символов будут информационными, а t символов - нулевыми. В случае ошибочного декодирования с высокой вероятностью, примерно равной 1-1/2^mt, избыточные символы будут отличны от нуля. Критерием для определения ошибочного декодирования информации является отличие от нуля хотя бы одного из t избыточных символов в обратном преобразовании Фурье, вычисленном после удаления ошибочных символов в коде Рида - Соломона.

Реализация блока восстановления информации 10 аналогична реализации блока вычисления обратного преобразования Фурье 4.

С выхода блока восстановления информации 10 информационные символы кода Рида - Соломона поступают на выход декодирующего устройства. С другого выхода блока восстановления информации 10

избыточные символы подают на вход дешифратора 11 ошибочного декодирования. В случае, если избыточные символы отличаются от нуля, дешифратор 11 ошибочного декодирования формирует сигнал ошибочного декодирования, который поступает на вход схемы ИЛИ 12.

Схема ИЛИ 12 выполняет функцию логического ИЛИ двух сигналов, свидетельствующих об отказе от декодирования. Первый сигнал поступает с блока вычисления локаторов ошибок 9. Он появляется, если многочлен локаторов ошибок не имеет решений. Второй сигнал поступает с блока восстановления информации 10. Этот сигнал появляется в случае, если избыточные символы кода Рида - Соломона, после обратного преобразования Фурье, отличаются от нуля.

Результирующий сигнал отказа от декодирования с выхода схемы ИЛИ 12 поступает на выход декодирующего устройства.

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

Например, помехоустойчивый код Рида - Соломона (22, 16), определенный над полем Галуа GF(2⁸) с минимальным кодовым расстоянием d_min=7, позволяет исправлять тройные ошибки. После определения местоположения трех ошибок и удаления их из кодового слова, получим укороченный код Рида - Соломона (19, 16). Для восстановления информации выполняют обратное преобразование Фурье укороченного кода (19, 16). В результате получаем 16 символов информации и 3 избыточных символа, которые используют для защиты от ошибочного декодирования информации. В случае, если хотя бы один из 3 избыточных символов отличается от нуля, формируют сигнал отказа от декодирования. При этом вероятность ошибочного декодирования не превысит величины 1/2 ²⁴.

Отметим также, что предлагаемое декодирующее устройство кода Рида - Соломона может быть реализовано как аппаратным, так и программно - аппаратным путем. В последнем случае включение уже существующих отдельных элементов ЭВМ (сумматоров, запоминающих устройств, регистров) в предлагаемое устройство дает выигрыш в объеме оборудования. Наибольшее сокращение аппаратных затрат дает программная реализация блоков вычисления обратного преобразования Фурье 4, блока вычисления синдрома 5, блока вычисления многочлена 6 принятых символов, блока решения ключевого уравнения 7, блока вычисления локаторов ошибок 9 и блока восстановления информации 10. В этих блоках осуществляют вычисления по формулам (1)...(5). Программная реализация с использованием алгоритмических языков программирования высокого уровня (Pascal, С и так далее) позволяет достаточно просто выполнять вычисления по формулам (1)...(5), причем вычисления по рекуррентным формулам (1)...(3) следует выполнять с использованием операторов цикла. При этом объем памяти для реализации декодирующего устройства составляет незначительную часть общих ресурсов памяти ЭВМ.

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

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