ПАРАЛЛЕЛЬНЫЙ РЕКОНФИГУРИРУЕМЫЙ КОДЕР РИДА-СОЛОМОНА Российский патент 2020 года по МПК H03M13/15 

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

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

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

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

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

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

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

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

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

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

Известен способ кодирования для кодера Рида-Соломона, описанный в патенте US 8151172 B2 с доработками предыдущего аналога EP 93310590.0, а именно, с заменой длинной цепи сумматоров на каскадное суммирование с определенными сигналами разрешения.

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

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

Недостатком кодера-прототипа является то, что в нем отсутствует возможность параллельного ввода данных, разрядность которых выше расширения поля Галуа.

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

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

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

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

Фиг. 1. Функциональная схема параллельного реконфигурируемого кодера Рида – Соломона для систематического кода Рида – Соломона, выполненная согласно изобретению.

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

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

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

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

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

Фиг. 7. Функциональная схема последовательного (А) и параллельного (Б) БИХ фильтра первого порядка, выполненная согласно изобретению.

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

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

$$\frac{m(x)\cdot x^{2t}}{g(x)}=q(x)+\frac{r(x)}{g(x)}$$ , (1)

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

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

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

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

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

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

$$c(x)=m(x)\cdot x^{2t}+r(x)$$ , (2)

где $$c(x)$$ - кодовое слово.

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

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

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

Рассмотрим более подробно функционирование заявленного параллельного реконфигурируемого кодера Рида-Соломона (Фиг. 1 - 8). Для реализации выражения (2) применяется схема РЛОС с представленная на Фиг. 1.

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

$$y(x)=\frac{m(x)\cdot x^{2t}}{g(x)}$$, (3)

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

$$z(x)=\frac{m(x)\cdot x^{2t}}{g(x)}-m(x)$$ (4)

Эквивалентная схема выражения (4) представлена на Фиг. 2. Домножив последнее слагаемое$$m(x)$$ в выражении (4) на$$\frac{x^{2t}}{g(x)}$$, и разделив соответственно, получим:

$$z(x)=\frac{m(x)\cdot x^{2t}}{g(x)}+\frac{m(x)\cdot x^{2t}}{g(x)}\cdot \frac{g(x)}{x^{2t}}$$ (5)

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

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

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

$$g(x)=(x-a)\cdot (x-a^1)\cdot \mathrm{....}\cdot (x-a^{2t})$$ , (6)

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

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

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

Для наилучшего применения схемы заявленного кодера в параллельном исполнении необходимо рассмотреть работу КИХ и БИХ фильтров на каждом такте работы. Тогда для первых четырех тактов работы выход БИХ фильтра можно записать:

$$\begin{array}{l}{y}_i=m_i+\underset{предыдущийтакт}{\underbrace{y_{i-1}\cdot a}};\\ y_{i+1}=m_{i+1}+y_i\cdot a=m_{i+1}+m_i\cdot a;\\ y_{i+2}=m_{i+2}+y_{i+1}\cdot a=m_{i+2}+m_{i+1}\cdot a+m_i\cdot a^2;\\ y_{i+3}=m_{i+3}+y_{i+2}\cdot a=m_{i+3}+m_{i+2}\cdot a+m_{i+1}\cdot a^2+m_i\cdot a^3+\underset{предыдущийтакт}{\underbrace{y_{i-1}\cdot a^4}}.\end{array}$$

Данное выражение можно продолжать сколь угодно долго для непрерывно поступающих данных. Согласно рассмотренного для четырех тактов выражения можно составить схему параллельного БИХ-фильтра представленного на Фиг. 7 (параметр распараллеливания равен 4). Аналогично можно построить схему параллельного КИХ-фильтра первого порядка. Таким образом, схему реконфигурируемого кодера Рида – Соломона с конвейеризацией, представленной на Фиг. 6, можно представить в параллельном виде, как показано на Фиг. 8. Все БИХ-фильтры (805) и КИХ-фильтры (805) состоят из аналогичных элементов, меняется лишь порядок умножителей с номером фильтра от 1 до Tmax.

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

Содержит:

- умножители в поле Галуа;

- параллельные фильтры БИХ первого порядка в количестве 2$${Т}_{\max }$$ штук;

- параллельные фильтры КИХ первого порядка в количестве 2$${Т}_{\max }$$ штук;

- элементы «И» включения\отключения определенных фильтров в общую цепь;

- регистры для конвейеризации схемы кодера;

- сумматоры в поле Галуа;

- элемент «И» включения\отключения фильтра БИХ;

Может быть реконфигурирован под любое количество исправляемых ошибок от $${Т}_{\max }$$ до 0, а также обладает высоким быстродействием ввиду возможности конвейеризации.

Позволяет осуществлять ввод/вывод данных в параллельном виде, поступающие с шины данных разрядностью выше разрешения поля Галуа.

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

При применении для кодов Рида – Соломона использует минимальные аппаратные ресурсы, сопоставимые с аналогичным нереконфигурируемым кодером.

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

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

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

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

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