Результат интеллектуальной деятельности: РЕКОНФИГУРИРУЕМЫЙ КОДЕР РИДА-СОЛОМОНА

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

Коды PC (Рида-Соломона) относятся к блочному кодированию, и их широко используют в системах хранения и передачи информации. Данные коды позволяют исправлять множественные ошибки, а также пакеты ошибок в больших блоках данных.

В настоящее время данные коды массово используют в таких системах хранения информации, как жесткие диски, твердотельные накопители, флэш-память и др., а также в стандартах цифровой передачи данных, например цифрового телевидения DVB. Таким образом, ввиду различного применения в одном устройстве необходимо использование кодов с разной корректирующей способностью соответственно. Например, для того чтобы в блоке данных используемый код позволял исправлять до 16 ошибок, необходимо применение определенного порождающего полинома определенной длины. Однако, для того чтобы в этом же блоке данных код позволял исправлять например 12 ошибок, необходимо применение другого порождающего полинома с меньшей длиной. То есть для использования одного и того же устройства с разными накопителями необходимо применение разных порождающих полиномов и, как следствие, разных кодеров, это приводит к увеличению аппаратных ресурсов. Однако использование кодера с регулируемой корректирующей способностью (переменный порождающий полином) может также удовлетворить различные требования к корректирующей способности.

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

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

Известен описанный в патенте ЕР 0608637 (А1) способ кодирования, который позволяет изменять корректирующую способность кода Рида-Соломона от максимально возможного количества исправляемых ошибок до 1.

Недостаток данного способа заключается в том, что ввиду увеличенного критического пути из-за большого количества последовательно соединенных сумматоров и элементов «И» (равного удвоенному количеству исправляемых ошибок) он обладает низким быстродействием.

В патенте US 8151172 (В2) описан способ кодирования, примененный в описанном выше способе кодирования, выполненном согласно патенту ЕР 0608637 (А1), но с заменой длинной цепи сумматоров на каскадное суммирование с определенными сигналами разрешения.

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

Наиболее близким к заявленному изобретению является кодер БЧХ-кодов, описанный в патенте US 8464141 В2, в котором проблему настраиваемости кодера под различную корректирующую способность решают путем разбиения порождающего полинома на отдельные множители (по определению, порождающий полином состоит из произведения примитивных неприводимых полиномов). Кодирование осуществляют путем деления информационных бит на минимальные полиномы, при этом используют регистр с линейной обратной связью (РЛОС). В зависимости от применяемой корректирующей способности используют цепи умножителей и делителей на примитивные полиномы разной длины. Этот кодер БЧХ-кодов выбран в качестве прототипа заявленного изобретения.

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

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

Поставленная задача решена путем создания реконфигурируемого кодера Рида-Соломона, содержащего массив элементов «И», цепь последовательно соединенных БИХ-фильтров первого порядка и цепь последовательно соединенных КИХ-фильтров первого порядка, причем по меньшей мере два БИХ-фильтра и по меньшей мере два КИХ-фильтра содержат управляющие элементы «И», при этом вход цепи БИХ-фильтров является входом кодера, а выход цепи БИХ-фильтров соединен с первым входом массива элементов «И», выход которого соединен со входом цепи КИХ-фильтров, выход которой является выходом кодера, а второй вход массива элементов «И» выполнен с возможностью получения сигналов разрешения или запрещения выдачи контрольных бит закодированных данных, при этом в течение первых k тактов работы кодера (k - количество информационных символов), при поданном на массив элементов «И» сигнале разрешения выдачи информационных данных, на выход кодера поступают данные с его входа, а в течение следующих 2t тактов работы кодера (2t - количество проверочных символов), при поданном на массив элементов «И» сигнале запрещения выдачи информационных данных, на выход кодера поступают сформированные кодером контрольные данные, причем вторые входы управляющих элементов «И» выполнены с возможностью получения сигналов разрешения, с помощью которых отключают фильтры с целью изменения корректирующей способности.

В предпочтительном варианте осуществления кодер конвейеризован дополнительными элементами задержки (регистрами), которые расположены в местах соединений соседних БИХ-фильтров или КИХ-фильтров цепи.

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

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

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

Фиг. 1. Функциональная схема кодера систематического кода Рида-Соломона.

Фиг. 2. Эквивалентная схема РЛОС с применением БИХ-фильтра.

Фиг. 3. Эквивалентная схема РЛОС с применением БИХ и КИХ-фильтров.

Фиг. 4. Эквивалентная схема кодера Рида-Соломона с применением БИХ и КИХ-фильтров.

Фиг. 5. Функциональная схема кодера Рида-Соломона с применением БИХ и КИХ-фильтров с коневейеризацией.

Фиг. 6. Функциональная схема реконфигурируемого кодера Рида-Соломона с применением БИХ и КИХ-фильтров с коневейеризацией, выполненная согласно изобретению.

Фиг. 7. Структурная схема декодера Рида-Соломона.

Рассмотрим принцип функционирования кодера Рида-Соломона (Фиг. 1-7).

Согласно определению кодов PC, систематическое кодирование осуществляют следующим образом:

где m(х) - входные незакодированные данные,

g(x) - порождающий полином,

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

q(x) - частное от деления,

r(х) - остаток от делении на g(x).

При этом результирующее кодовое слово (закодированные данные) в систематическом виде представляют как

где с(х) - кодовое слово.

Таким образом, данные на выходе кодера остаются неизменными, однако к ним добавляется контрольные данные r(х). Все математические операции осуществляются в поле Галуа GF(2^p).

Аппаратно выражение (2) реализуют при помощи регистра с линейной обратной связью (РЛОС). Первые k тактов (k - количество информационных символов) работы кодера данные проходят на выход кодера неизменными, при этом одновременно поступают на вход РЛОС (регистра с линейной обратной связью), где с учетом обратной связи происходит вычисление остатка r(x). После k тактов работы кодера в схеме РЛОС отключают обратную связь и значение остатка r(х) фиксируют в сдвиговом регистре. В течение последующих 2t тактов (2t - количество проверочных символов) из схемы РЛОС выгружают и подают на выход кодера значение остатка r(х).

При необходимости изменения требований к корректирующей способности кода PC, изменяют порождающий полином g(x), что приводит к изменению схемы РЛОС. Заявленное изобретение включает в себя способ построения схемы деления на порождающий полином с возможностью минимальными затратами изменять порождающий полином в процессе работы.

Для реализации выражения (2) применяют схему РЛОС, представленную на Фиг. 1.

Когда переключатели P1, Р2 101, 102 находятся в положении 1, схема РЛОС принимает вид схемы БИХ-фильтра (фильтр с бесконечной импульсной характеристикой) с отличием в том, что выход кодера не совпадает с выходом БИХ-фильтра. А именно выходом РЛОС z(x) является выход сдвигового регистра 103, однако в БИХ-фильтре с подобной реализацией выходом данных y(х) является выход сумматора 104. Опишем математически работу схемы РЛОС при включенных переключателях P1, Р2 101, 102, а именно находящихся в положении 1. Выход y(х) БИХ-фильтра можно записать следующим образом:

Однако выход z(x) РЛОС применительно для кодирования отличается, так как выведен до сумматора (104 или 201), а именно:

Эквивалентная схема выражения (4) представлена на Фиг. 2. Домножив последнее слагаемое m(х) в выражении (4) на и разделив соответственно, получаем

Все математические операции осуществляют в поле Галуа GF(2^p), поэтому вычитание заменяют суммированием. Эквивалентная схема выражения (5) представлена на Фиг. 3.

После включения переключателей P1, Р2 101, 102 в положение 2 в схеме кодера на Фиг. 1 отключают цепь обратной связи, а на вход кодера подают ноль. В эквивалентной схеме кодера на Фиг. 3 на вход КИХ-фильтра (фильтра с конечной импульсной характеристикой) вместо выхода БИХ-фильтра подают ноль. Так как первые k тактов работы кодера на его выход по определению систематического кодирования выдают данные без изменения, а последующие 2t тактов выдают данные, вычисленные кодером, то можно пренебречь сумматором 301 в схеме кодера на Фиг. 3, добавить переключатель Р3 401 и получить эквивалентную схему всего кодера, представленную на Фиг. 4. То есть первые k тактов работы кодера на его выход 402 поступают данные после БИХ 403 и КИХ 404 (фильтр с конечной импульсной характеристикой) фильтров, соединенных последовательно, а так как оба фильтра имеют один и тот же полином, данные на выход кодера будут поступать без изменений, что и требуется по определению кодера систематического кода Рида-Соломона. Однако в эту фазу выполняют вычисление и после k-го такта БИХ-фильтр 403 из цепи отключают с помощью переключателя Р3 (401) по сигналу data_ecc 405, после чего продолжает работать лишь КИХ-фильтр (404), который подает на выход (402) кодера значения контрольных символов.

Такое построение эквивалентной схемы (Фиг. 4) позволяет избежать общей цепи обратной связи 105, охватывающей всю схему РЛОС, как в схеме кодера на Фиг. 1. Порождающий полином g(x) для кодов Рида-Соломона представим в виде

где а∈GF(2^p) - примитивный элемент поля Галуа размерности р.

Таким образом, схемы БИХ- и КИХ-фильтров можно разбить на последовательно соединенные фильтры первого порядка 504 - БИХ, 505 - КИХ, как показано на Фиг. 5. Переключатель 401 при этом заменяют на побитовый элемент «И» (506). А так как в таком построении схемы отсутствует общая цепь обратной связи с выхода на вход кодера, для уменьшения критического пути через цепь последовательно соединенных сумматоров конвейеризуют схему дополнительными регистрами 501, 502, например pipe1 и pipe2 и так далее при необходимости, при этом сегментируют схему на меньшие участки по критическому пути. При этом латентность кодера увеличивается на число тактов, равное количеству дополнительных конвейерных регистров, зато быстродействие становится крайне высоким.

Наилучшее применение схемы на Фиг. 5 получается при использовании дополнительных сигналов (t=Tmax, t=Tmax-1, t=Tmax-2, …, t=1) разрешения определенных фильтров 603, как показано на Фиг. 6. На Фиг. 6 представлена функциональная схема варианта выполнения заявленного реконфигурируемого кодера PC с возможной конвейеризацией. Данная схема наделяет код корректирующей способностью от максимально возможного количества исправляемых ошибок Tmax до 1. Из выражения (6) известно, что для того, чтобы код позволял исправлять t ошибок, необходим порождающий полином степени 2t. Таким образом, схема заявленного реконфигурируемого кодера рассчитана на полином максимальной степени 2Tmax. При необходимости кодировать данные кодом с числом исправляемых ошибок меньше максимального Tmax, необходимо с помощью сигналов разрешения 603 отключить определенные фильтры (то есть часть множителей в полиноме (6) заменить на 1), и результирующий полином получают необходимой степени, а значит, с заданной корректирующей способностью. Например, для кода с максимальным количеством ошибок, которые могут быть исправлены равным t=Tmax-1, необходимо деактивировать по два крайних правых фильтра БИХ 604 и КИХ 605. Для кода с количеством исправляемых ошибок, равным t=Tmax-2, необходимо деактивировать по четыре крайних правых фильтра БИХ и КИХ.

Рассмотрим более подробно представленный на Фиг. 6 вариант выполнения заявленного реконфигурируемого кодера Рида-Соломона. Реконфигурируемый кодер Рида-Соломона содержит цепь последовательно соединенных БИХ-фильтров 604 первого порядка и цепь последовательно соединенных КИХ-фильтров 605 первого порядка, между которыми расположен массив элементов «И». Два БИХ-фильтра 604 и два КИХ-фильтра 605 содержат управляющие элементы «И». Вход цепи БИХ-фильтров 604 является входом кодера m(x), а выход цепи БИХ-фильтров 605 соединен с первым входом массива элементов «И», выход которого соединен со входом цепи КИХ-фильтров 605, выход которой является выходом кодера с(х). Второй вход массива элементов «И» выполнен с возможностью получения сигналов data_ecc разрешения или запрещения выдачи контрольных бит закодированных данных, при этом в течение первых k тактов работы кодера (k - количество информационных символов), при поданном на массив элементов «И» сигнале data_ecc разрешения выдачи информационных данных, на выход кодера поступают данные с его входа, а в течение следующих 2t тактов работы кодера (2t - количество проверочных символов), при поданном на массив элементов «И» сигнале запрещения выдачи информационных данных, на выход кодера с(х) поступают сформированные кодером контрольные данные. Вторые входы управляющих элементов «И» выполнены с возможностью получения сигналов разрешения (t=Tmax, t=Tmax-1, t=Tmax-2, …, t=1), с помощью которых отключают фильтры с целью изменения корректирующей способности.

Заявленный кодер конвейеризован дополнительными элементами задержки (регистрами) 506, которые расположены в местах соединений соседних БИХ-фильтров 604 или КИХ-фильтров 605 цепи.

Два первых БИХ-фильтра 604 и два первых КИХ-фильтра 605 в цепи содержат последовательно соединенные умножитель, сумматор и элемент задержки.

Последующие (за первыми двумя) БИХ-фильтры 604 и КИХ-фильтры 605 в цепи содержат последовательно соединенные умножитель, управляющий элемент «И», сумматор и элемент задержки, при этом выход умножителя соединен с первым входом управляющего элемента «И», выход которого соединен со входом элемента задержки, а второй вход управляющего элемента «И» выполнен с возможностью получения сигнала разрешения (t=Tmax, t=Tmax-1, t=Tmax-2, …, t=1), с помощью которого отключают фильтр.

Декодирование кодов Рида-Соломона структурно показано на Фиг. 7. Принятые данные (с возможными ошибками) v(x) поступают в схему декодера, одновременно происходит запись этих данных в буфер FIFO. Декодирование поделено на четыре основных этапа. Сначала данные поступают в схему вычисления синдромов (признаки ошибок), первые n тактов, потому как кодовое слово стало длины n. Дальнейшие вычисления декодер проводит с вычисленными синдромами. Следующий этап - вычисление полинома локаторов ошибок. Например, в алгоритме Берлекэмпа - Мэсси (ВМА) без инверсии для данного этапа требуется 2t тактов (где t - количество исправляемых ошибок, с которым было закодировано переданное кодовое слово). Далее вычисленные коэффициенты уравнения поступают в схемы поиска позиций ошибок и в схему поиска значений ошибок. После вычисления полинома значений ошибок этот полином вместе с указателями позиций ошибок из схемы поиска позиций ошибок подают на схему составления вектора ошибок. Данная схема формирует маску е(х) для исправления искаженных данных v(x) при считывании из буфера FIFO. При фиксированном параметре m поля Галуа декодер, реконфигурируемый по количеству исправляемых ошибок, реализуют путем изменения количества тактов, необходимых для работы алгоритма ВМА и схемы поиска значений ошибок. Таким образом, при добавлении к схеме декодера управления в зависимости от параметра t (максимальное количество исправляемых ошибок) декодер становится реконфигурируемым в зависимости от корректирующей способности, с которой было закодировано кодовое слово.

Заявленный реконфигурируемый кодер Рида-Соломона содержит умножители в поле Галуа, фильтры БИХ первого порядка в количестве 2T_max штук, фильтры КИХ первого порядка в количестве 2T_max штук, управляющие элементы «И» включения/отключения фильтров в общую цепь, регистры для конвейеризации схемы кодера, сумматоры в поле Галуа, элементы «И» включения/отключения фильтров БИХ.

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

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

- позволяет кодировать данные кодом Рида-Соломона с разной корректирующей способностью, то есть количеством исправляемых ошибок (символов) от T_max до 1;

- обладает крайне высоким быстродействием ввиду минимальных критических путей между тактируемыми регистрами из-за возможности вставки конвейерных регистров между фильтрами;

- использует минимальные аппаратные ресурсы, сопоставимые с аналогичным нереконфигурируемым кодером;

- предельно прост в управлении: если перед загрузкой данных инициализируют сигналы разрешения (например, t>Tmax-1 - для количества исправляемых ошибок, равного Tmax, или t>Tmax-3 - для количества исправляемых ошибок, равного Tmax-2) определенных фильтров, при этом включают те фильтры, которые необходимы для заданного количества исправляемых ошибок; первые k тактов работы кодера загружают данные, при этом сигнал data_ecc в состоянии «1», после чего обнуляют сигнал data_ecc и следующие 2t тактов происходит выгрузка контрольных символов данных.

Заявленный кодер может быть реализован в одном из следующих устройств: контроллер жестких дисков, дисков SSD, контроллер NAND-flash памяти, IP-блок в составе СнК и др.

Реконфигурируемый декодер кодов Рида-Соломона содержит схему вычисления синдромов; схему вычисления полинома локаторов ошибок (по алгоритму ВМА без инверсии); схему поиска значений ошибок; схему поиска позиций ошибок; схему составления вектора ошибок; буфер FIFO для хранения принятых, но неисправленных данных; схему исправления ошибок (XOR).

Декодер кодов PC является реконфигурируемым по корректирующей способности. А именно декодер при фиксированном расширении m поля Галуа GF(2^m) может исправлять количество ошибок от t_max до 1, в зависимости от конфигурации закодированного слова. Это осуществляют путем изменения количества тактов для работы алгоритма ВМА от 2t_max до 1, а также количества тактов для работы схемы поиска позиций ошибок от t_max до 1.

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