Параллельный кодер бчх с реконфигурируемой корректирующей способностью
Владельцы патента RU 2777527:
Акционерное общество Научно-производственный центр «Электронные вычислительно-информационные системы» (АО НПЦ «ЭЛВИС») (RU)
Изобретение относится к области цифровой обработки информации. Техническим результатом изобретения является создание параллельного кодера БЧХ с реконфигурируемой корректирующей способностью, который обладает повышенной эффективностью, скоростью работы, функциональностью и универсальностью. Это достигается тем, что кодер позволяет кодировать данные в соответствии с различными характеристиками кодов БЧХ, такими как количество исправляемых ошибок, длина данных; позволяет обрабатывать данные, поступающие на кодер с шины данных, параллельно и выдавать контрольные биты информации также в параллельном виде; использует многовходовые сумматоры, имеющие структуру двоичного дерева, что позволяет существенно сократить задержку вычислений. 8 ил., 1 табл.
Изобретение относится к области цифровой обработки информации (сигналов), а именно к параллельным кодерам БЧХ (Боуза – Чоудхури – Хоквингема) с реконфигурируемой корректирующей способностью, и может быть использовано для помехоустойчивого кодирования информации с переменной корректирующей способностью в различных системах передачи и хранения данных.
Коды Боуза — Чоудхури — Хоквингема (БЧХ-коды) — это широкий класс циклических кодов, применяемых для защиты информации от ошибок. Отличается возможностью построения кода с заранее определёнными корректирующими свойствами, а именно, минимальным кодовым расстоянием.
Коды БЧХ широко используют в системах передачи и хранения данных, таких как твердотельные накопители данных, проводные и беспроводные коммуникации, цифровое телевидение и другие. Данные коды позволяют исправлять множественные ошибки в блоках данных от нескольких бит до нескольких килобайт.
При этом при реализации аппаратного кодера БЧХ возникает ряд проблем.
Во-первых, в рамках одного устройства или системы могут требоваться коды БЧХ с разной корректирующей способностью. Это означает необходимость применения порождающих полиномов разной длины, что, в общем, означает использование разных кодеров БЧХ и увеличение аппаратных затрат. Более эффективным решением является использование кодера БЧХ с регулируемой корректирующей способностью, то есть с переменным порождающий полиномом, способного удовлетворить различные требования к корректирующей способности.
Во-вторых, для использования кодирования БЧХ в системах хранения данных возникает необходимость кодировать данные, поступающие параллельно, то есть с шины данных. Это означает, что последовательное кодирование таких данных приведёт к значительному замедлению их передачи, и для обеспечения высокого быстродействия необходимо использовать параллельный кодер БЧХ.
Известен (патент CN101068113) кодер БЧХ, в котором проблема параллельности для входного потока данных решена. Кодер рассчитан на ввод и вывод данных под настраиваемую ширину шины данных для аппаратной реализации в конкретном применении.
Недостатком данного кодера является то, что он не является реконфигурируемым под различную корректирующую способность в процессе работы, а именно, полином для кодирования с заданным максимальным числом исправляемых ошибок остается неизменным в аппаратной реализации. Это ухудшает эффективность работы данного кодера.
Известен (патент CN 102761340) кодер БЧХ, в котором проблема параллельности для входного потока данных решена. Кодер рассчитан на ввод и вывод данных под фиксированную ширину шины данных 8 бит.
Недостатком данного кодера является то, что в нем отсутствует способ построения схемы для настраиваемой ширины шины входных данных. Это ухудшает эффективность работы данного кодера.
Известен (патент CN 101227194) кодер БЧХ, в котором проблема параллельности для входного потока данных решена. Кодер рассчитан на ввод и вывод данных под настраиваемую ширину шины данных для аппаратной реализации в конкретном применении.
Недостатком данного кодера является то, что он не является реконфигурируемым под различную корректирующую способность в процессе работы, а именно, полином для кодирования с заданным максимальным числом исправляемых ошибок остается неизменным в аппаратной реализации. Это ухудшает эффективность работы данного кодера.
Известен (патент CN 102820892) кодер БЧХ, в котором проблема параллельности для входного потока данных решена.
Недостатком данного кодера является то, что он рассчитан на ввод и вывод данных под настраиваемую ширину шины данных для аппаратной реализации в конкретном применении, однако обладает сложной системой мультиплексирования, к тому же данный кодер не является реконфигурируемым под изменение корректирующей способности в процессе работы. Это ухудшает эффективность работы данного кодера.
Наиболее близким к заявленному изобретению является кодер БЧХ (патент US 8,812,940 B2), в котором проблема настраиваемого кодера под различную корректирующую способность решена путем разбиения порождающего полинома на отдельные множители (по определению, порождающий полином состоит из произведения примитивных неприводимых полиномов). Кодирование осуществляют путем деления информационных бит на минимальные полиномы. В зависимости от применяемой корректирующей способности, используют разные ответвления от общей цепи последовательно соединенных регистров с линейной обратной связью. Данный кодер БЧХ выбран в качестве прототипа заявленного изобретения.
Кодер прототип удовлетворяет требованию реконфигурируемости кодера под различную корректирующую способность, однако в нем в последовательном виде, то есть, за один такт работы схемы на вход поступает один символ данных. Таким образом, такая схема не применима для случая, когда данные на вход кодера поступают с шины данных, то есть параллельно, а именно за один такт работы схемы поступает сразу несколько символов данных. Это ухудшает функциональность и универсальность применения данного кодера.
Техническим результатом изобретения является создание параллельного кодера БЧХ с реконфигурируемой корректирующей способностью, который обладает повышенной эффективностью, скоростью работы, функциональностью и универсальностью за счет того, что: позволяет кодировать данные в соответствии с различными характеристиками кодов БЧХ, такими как количество исправляемых ошибок, длина данных и др.; позволяет обрабатывать данные, поступающие на кодер с шины данных, параллельно, и выдавать контрольные биты информации также в параллельном виде; использует многовходовые сумматоры, имеющие структуру двоичного дерева, что позволяет существенно сократить задержку вычислений.
Поставленный технический результат достигнут путем создания параллельного кодера БЧХ с реконфигурируемой корректирующей способностью, который осуществляет помехоустойчивое кодирование входных данных с помощью кодов БЧХ (Боуза – Чоудхури – Хоквингема), и характеризуется
- параметром n, который является длиной входного сообщения u(x),
- параметром k, который является длиной порождающего полинома g(x),
- параметром q, который определяет количество элементов входного сообщения u(x), обрабатываемых параллельно,
- входными данными кодера БЧХ является входное сообщение u(x), представленное вектором u = (un−1,un−2,...,u1,u0),
- входными данными кодера БЧХ является порождающий полином g(x), представленный вектором g = (gk−1,gk−2,...,g1,g0),
- выходными данными кодера БЧХ является выходное сообщение v(x), представленное вектором v = (vn+k−1,vn+k−2,...,v1,v0),
- выходные данные кодера БЧХ v(x) состоят из элементов входных данных u(x) и элементов остатка r(x), (vn+k−1,vn+k−2,...,v1,v0) = (rk−1,rk−2,...,r1,r0,un−1,un−2,...,u1,u0),
- при параллельной обработке входные данные кодера БЧХ (un−1,un−2,...,u1,u0) могут быть представлены двумерным массивом (uh,i), где (h = 0,1,...,q−1), i – номер такта, на котором поступают входные данные, (i = 0,1,...,[n/q]−1), где [n/q] – целая часть от деления n/q с округлением в большую сторону;
- кодер БЧХ содержит регистры z = (zk−1,zk−2,...,z1,z0) [1], в которых в процессе кодирования формируются значения остатка r(x),
- кодер БЧХ содержит регистры, хранящие значения коэффициентов Ch,j, где (h = 0,1,...,q−1), (j = 0,1,...,k−1),
- кодер БЧХ содержит массив элементов суммирования [2] с индексами (j = 0,1,...,k−1), представляющих собой многовходовые сумматоры, имеющие структуру двоичного дерева,
- кодер БЧХ содержит двумерный массив умножителей [3] с индексами (h,j), где (h = 0,1,...,q−1), (j = 0,1,...,k−1),
- кодер БЧХ содержит массив сумматоров [4] с индексами (h = 0,1,...,q−1),
- вход каждого регистра zj соединён с выходом соответствующего элемента суммирования [2], где (j = 0,1,...,k−1),
- каждый элемент суммирования [2] с индексом (j = 0,1,...,q−1) имеет (q) входов,
- каждый элемент суммирования [2] с индексом (j = q,q+1,...,k−1) имеет (q+1) вход,
- входы каждого элемента суммирования [2] с индексом (j = 0,1,...,q−1) соединены с выходами умножителей [3] с индексами (h,j), где (h = 0,1,...,q−1),
- входы каждого элемента суммирования [2] с индексом (j = q,q+1,...,k−1) соединены с выходами умножителей [3] с индексами (h,j), где (h = 0,1,...,q−1), а также с выходом регистра zj−q,
- первый вход каждого умножителя [3] с индексами (h,j), где (h = 0,1,...,q−1), (j = 0,1,...,k−1), соединён с выходом регистра, содержащего коэффициент Ch,j,
- второй вход каждого умножителя [3] с индексами (h,j), где (h = 0,1,...,q−1), (j = 0,1,...,k−1), соединён с выходом сумматора [4] с индеком (h) для любого индекса (j),
- первый вход каждого сумматора [4] с индекcом (h = 0,1,...,q−1) соединён с выходом регистра zh+k−q,
- второй вход каждого сумматора [4] с индекcом (h = 0,1,...,q−1) соединён с элементом входных данных uq−h−1,i.
Для лучшего понимания заявленного изобретения далее приводится его подробное описание с соответствующими графическими материалами.
Фиг. 1. Схема последовательного кодера БЧХ, известного из уровня техники.
Фиг. 2. Схема параллельного кодера БЧХ, известного из уровня техники.
Фиг. 3. Критический путь параллельного кодера БЧХ, известного из уровня техники.
Фиг. 4. Схема последовательного многовходового сумматора, известного из уровня техники.
Фиг. 5. Схема многовходового сумматора, имеющего структуру двоичного дерева, известного из уровня техники.
Фиг. 6. Схема ускоренного параллельного кодера БЧХ для случая k=7, q=4, выполненного согласно изобретению.
Фиг. 7. Схема ускоренного параллельного кодера БЧХ для случая k≥q, выполненного согласно изобретению.
Фиг. 8. Схема ускоренного параллельного кодера БЧХ для случая k≥q с номерами элементов, выполненного согласно изобретению.
Табл. 1. Пример заданных порождающих полиномов со степенями 8 и 5.
Из определения кодов БЧХ, систематическое кодирование осуществляют следующим образом:
, (1)
где
– входные незакодированные данные,
– порождающий полином,
– частное от деления 
,
– остаток от деления ,
– длина входных незакодированных данных ,
– длина остатка .
При этом результирующее кодовое слово (закодированные данные) в систематическом виде определяют следующим выражением:
, (2)
Таким образом, входные данные на выходе кодера остаются неизменными, однако к ним добавляют контрольные данные .
Для реализации выражения (2) применяют схему на основе регистра с линейной обратной связью (РЛОС) с настраиваемыми коэффициентами порождающего полинома и узлами управления, представленную на Фиг. 1. Перед началом кодирования инициализируют регистры, которые хранят значения коэффициентов 
порождающего полинома . Также перед началом кодирования инициализируют все элементы РЛОС (регистры 
) нулевыми значениями. Первые тактов работы устройства данные без изменений проходят на выход схемы, и одновременно поступают на вход РЛОС. Переключатели P1, P2 находятся в положении I. В течение этой фазы работы устройства происходит вычисление остатка . После тактов работы, переключатели P1, P2 переходят в состояние II, и тем самым отключают петлю обратной связи, и подключают РЛОС к выходу схемы. Последующие тактов происходит выгрузка остатка из регистров 
.
Значения входных и выходных данных регистров 
определяют следующими формулами:
, 
, 
, (3)
, 
, , 
. (4)
При необходимости изменения требований к корректирующей способности кода БЧХ, изменяют порождающий полином . Арифметические операции в выражении (2), а также в схеме на Фиг. 1, выполняют в расширенном поле Галуа 
. Так как порождающий полином можно задавать любой степени (от максимального количества значащих коэффициентов 
до 
), кодер является реконфигурируемым под требуемое количество исправляемых ошибок (от максимального 
до 1) для выбранного кода БЧХ. Для изменения корректирующей способности кода, перед этапом кодирования перезаписывают коэффициенты порождающего полинома . При этом учитывают, что значащий коэффициент при самой старшей степени полинома должен быть на месте регистра 
, поэтому, если требуемый полином имеет степень меньшую, чем заложено в фактической аппаратной реализации , тогда регистры при младших степенях обнуляют. В таблице 1 показан пример, в случае если порождающие полиномы имеют степень 8, и следующей строкой со степенью 5. Коэффициент при старшей степени в кодах БЧХ всегда равен 1, поэтому в таблице он не приведен.
Наилучшее применение схема заявленного кодера БЧХ находит в кодировании двоичных кодов БЧХ. Для двоичных кодов БЧХ умножители в поле Галуа 
в схеме Фиг. 1 заменяют логическим элементом «AND», а сумматоры — логическим элементом «XOR». Регистры, хранящие коэффициенты порождающего полинома , в такой схеме являются одноразрядными.
В схеме кодера БЧХ, представленной на Фиг. 1, значения 
, поступающие на входы регистров , определяют выражением (3). Также из схемы на Фиг. 1 и из выражения (4) видно, что значения регистров являются просто задержанными на один такт соответствующими значениями . Из этого следует, что вместо задержки на один такт в регистрах , значения могут быть сдвинуты на одну позицию вправо и использованы в том же такте для обработки следующего элемента входных данных 
. Это утверждение можно распространить на последующие такты, вплоть до такта номер 
, обрабатывая таким образом одновременно до 
элементов входных данных . Т.е. теоретически возможна обработка за один такт всех элементов входных данных .
Схема, реализующая параллельное кодирование 
элементов входных данных , приведена на Фиг. 2.
В случае параллельного кодирования входные данные разбивают на группы по 
элементов. Таким образом, количество тактов работы схемы уменьшают в (размерность шины данных) раз с 
до 
, где – целая часть от деления 
с округлением в большую сторону. К моменту такта входные данные заканчиваются, и вычисленные контрольные символы хранят в регистрах . Для ускорения схемы контрольные символы из регистров также можно считывать параллельно.
Рекуррентная формула, определяющая значения 
:
, , 
, (5)
, , 
, , (6)
где
– значение 
-го символа слова данных , поступивших в 
-ый такт,
– целая часть от деления с округлением в большую сторону.
Недостатком параллельного кодера БЧХ, схема которого представлена на Фиг. 2, являются достаточно длинные критические пути, которые линейно зависят от степени параллелизма, то есть от значения параметра . Быстродействие цифровой схемы определяется ее критическими путями – путями распространения логического сигнала, имеющими наибольшую задержку. Критические пути рассмотренного параллельного кодера БЧХ содержат те функциональные элементы, через которые последовательно проходит логический сигнал, начиная от текущих значений 
, поступающих с выходов соответствующих регистров , до входов этих же регистров .
Пример критического пути рассмотренного параллельного кодера БЧХ показан на Фиг. 3 серой полупрозрачной линией. Критический путь содержит элементов умножения и 
элементов сложения, т.е. задержка этого пути может быть вычислена по формуле:
, (7)
где
– задержка на сумматоре,
– задержка на умножителе.
Целью заявленного изобретения является повышение быстродействия параллельного реконфигурируемого кодера БЧХ, то есть задача состоит в том, чтобы, не меняя функциональность, преобразовать схему на Фиг. 2 таким образом, чтобы существенно сократить время задержки вычислений.
Известно, что суммирование большого числа слагаемых может быть организовано различными способами, и от способа организации суммирования будет зависеть задержка вычислений. На Фиг. 4 представлена схема сумматора восьми переменных, имеющего последовательную структуру. Как следует из приведенной схемы, время задержки такого сумматора равно:
,
где
– количество входных переменных,
– задержка на сумматоре.
Другой способ организации вычислений — использование сумматора со структурой бинарного дерева, схема которого представлена на рисунке 5. Именно такая структура сумматора позволяет минимизировать задержку вычислений, которая для рассматриваемого случая будет равна:
где
– количество входных переменных,
– двоичный логарифм от с округлением в большую сторону,
– задержка на сумматоре.
Основная идея заявленного изобретения заключается в том, чтобы преобразовать известную схему параллельного реконфигурируемого кодера БЧХ, приведённую на Фиг. 2, таким образом, чтобы результаты кодирования, т.е. значения , вычислялись с помощью сумматоров, имеющих структуру бинарного дерева, и таким образом существенно уменьшить время задержки вычислений.
На каждом 
-ом такте, во время которого подаются входные данные, кодер должен вычислить новые значения регистров :
, , .
Исходным для построения существующей схемы параллельного реконфигурируемого кодера БЧХ является набор рекуррентных соотношений (5,6). Используя эти соотношения, можно выразить значения 
через 
для любого и для любого 
:
,
,
,
и так далее.
Тогда общая формула для 
будет иметь следующий вид:
, (7)
, (8)
где
,
,
,
,
– коэффициент, который зависит только от значений элементов 
.
Рекуррентная формула для коэффициентов :
,
,
где
,
.
Используя соотношения (7,8), можно выразить значения 
через 
:
, (9)
где
,
,
.
Используя выражение (9) можно построить схему ускоренного параллельного кодера БЧХ. Причём схемы будут различными для ситуаций 
и 
. В рамках данной заявки будет приведена схема для ситуации , поскольку она более актуальна для практического применения.
Пример схемы кодера, реализующего выражение (9) для случая 
, 
, приведён на Фиг. 6. Схема кодера, реализующего выражение (9) для случая , приведена на Фиг. 7.
Элементы «tree», изображенные в правой части схемы, являются многовходовыми сумматорами, т.е. получают на вход от 1 до 
слагаемых, и реализуют структуру бинарного дерева, как показано на Фиг. 5, что позволяет минимизировать задержку.
Общая задержка вычислений для данной схемы (для худшего случая 
) определяется формулой:
Эта задержка значительно меньше той, что была получена в схеме существующего параллельного реконфигурируемого БЧХ кодера, и различие будет тем больше, чем больше значение 
.
Аппаратной реализацией заявленного изобретения является IP-блок параллельного кодера БЧХ, схема которого приведена на Фиг. 10 и Фиг. 11.
Заявленный кодер БЧХ осуществляет помехоустойчивое кодирование входных данных с помощью кодов Боуза – Чоудхури – Хоквингема.
Заявленный кодер БЧХ характеризуется параметром n, который является длиной входного сообщения u(x).
Заявленный кодер БЧХ характеризуется параметром k, который является длиной порождающего полинома g(x).
Заявленный кодер БЧХ характеризуется параметром q, который определяет количество элементов входного сообщения u(x), обрабатываемых параллельно.
Входными данными заявленного кодера БЧХ является входное сообщение u(x), представленное вектором u = (un−1,un−2,...,u1,u0).
Входными данными заявленного кодера БЧХ является порождающий полином g(x), представленный вектором g = (gk−1,gk−2,...,g1,g0).
Входными данными заявленного кодера БЧХ является выходное сообщение v(x), представленное вектором v = (vn+k−1,vn+k−2,...,v1,v0).
Входные данные заявленного кодера БЧХ v(x) состоят из элементов входных данных u(x) и элементов остатка r(x), (vn+k−1,vn+k−2,...,v1,v0) = (rk−1,rk−2,...,r1,r0,un−1,un−2,...,u1,u0).
При параллельной обработке входные данные заявленного кодера БЧХ (un−1,un−2,...,u1,u0) могут быть представлены двумерным массивом (uh,i), где (h = 0,1,...,q−1), i – номер такта, на котором поступают входные данные, (i = 0,1,...,[n/q]−1), где [n/q] – целая часть от деления n/q с округлением в большую сторону.
Хотя описанный выше вариант выполнения заявленного изобретения был изложен с целью иллюстрации заявленного изобретения, специалистам ясно, что возможны разные модификации, добавления и замены, не выходящие из объема и смысла заявленного изобретения, раскрытого в прилагаемой формуле изобретения.
| Индекс регистра g | 0 | 1 | 2 | ... | k-9 | k-8 | k-7 | k-6 | k-5 | k-4 | k-3 | k-2 | k-1 |
| Коэффициенты полинома при k=8 | 0 | 0 | 0 | ... | 0 | g0 | g1 | g2 | g3 | g4 | g5 | g6 | g7 |
| Коэффициенты полинома при k=5 | 0 | 0 | 0 | ... | 0 | 0 | 0 | 0 | g0 | g1 | g2 | g3 | g4 |
Таблица 1
Параллельный кодер БЧХ с реконфигурируемой корректирующей способностью, который осуществляет помехоустойчивое кодирование входных данных с помощью кодов БЧХ (Боуза – Чоудхури – Хоквингема) и характеризуется
- параметром n, который является длиной входного сообщения u(x),
- параметром k, который является длиной порождающего полинома g(x),
- параметром q, который определяет количество элементов входного сообщения u(x), обрабатываемых параллельно,
- входными данными кодера БЧХ является входное сообщение u(x), представленное вектором u = (un−1,un−2,...,u1,u0),
- входными данными кодера БЧХ является порождающий полином g(x), представленный вектором g = (gk−1,gk−2,...,g1,g0),
- выходными данными кодера БЧХ является выходное сообщение v(x), представленное вектором v = (vn+k−1,vn+k−2,...,v1,v0),
- выходные данные кодера БЧХ v(x) состоят из элементов входных данных u(x) и элементов остатка r(x), (vn+k−1,vn+k−2,...,v1,v0) = (rk−1,rk−2,...,r1,r0,un−1,un−2,...,u1,u0),
- при параллельной обработке входные данные кодера БЧХ (un−1,un−2,...,u1,u0) могут быть представлены двумерным массивом (uh,i), где (h = 0,1,...,q−1), i – номер такта, на котором поступают входные данные, (i = 0,1,...,[n/q]−1), где [n/q] – целая часть от деления n/q с округлением в большую сторону;
- кодер БЧХ содержит регистры z = (zk−1,zk−2,...,z1,z0) [1], в которых в процессе кодирования формируются значения остатка r(x),
- кодер БЧХ содержит регистры, хранящие значения коэффициентов Ch,j, где (h = 0,1,...,q−1), (j = 0,1,...,k−1),
- кодер БЧХ содержит массив элементов суммирования [2] с индексами (j = 0,1,...,k−1), представляющих собой многовходовые сумматоры, имеющие структуру двоичного дерева,
- кодер БЧХ содержит двумерный массив умножителей [3] с индексами (h,j), где (h = 0,1,...,q−1), (j = 0,1,...,k−1),
- кодер БЧХ содержит массив сумматоров [4] с индексами (h = 0,1,...,q−1),
- вход каждого регистра zj соединён с выходом соответствующего элемента суммирования [2], где (j = 0,1,...,k−1),
- каждый элемент суммирования [2] с индексом (j = 0,1,...,q−1) имеет (q) входов,
- каждый элемент суммирования [2] с индексом (j = q,q+1,...,k−1) имеет (q+1) вход,
- входы каждого элемента суммирования [2] с индексом (j = 0,1,...,q−1) соединены с выходами умножителей [3] с индексами (h,j), где (h = 0,1,...,q−1),
- входы каждого элемента суммирования [2] с индексом (j = q,q+1,...,k−1) соединены с выходами умножителей [3] с индексами (h,j), где (h = 0,1,...,q−1), а также с выходом регистра zj−q,
- первый вход каждого умножителя [3] с индексами (h,j), где (h = 0,1,...,q−1), (j = 0,1,...,k−1), соединён с выходом регистра, содержащего коэффициент Ch,j,
- второй вход каждого умножителя [3] с индексами (h,j), где (h = 0,1,...,q−1), (j = 0,1,...,k−1), соединён с выходом сумматора [4] с индеком (h) для любого индекса (j),
- первый вход каждого сумматора [4] с индекcом (h = 0,1,...,q−1) соединён с выходом регистра zh+k−q,
- второй вход каждого сумматора [4] с индекcом (h = 0,1,...,q−1) соединён с элементом входных данных uq−h−1,i.
