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

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

Коды БЧХ (Боуза - Чоудхури - Хоквингема) относятся к блочному кодированию и широко используются в системах хранения и передачи информации. Эти коды позволяют исправлять множественные ошибки в блоках данных длиной от нескольких бит до нескольких килобайт (дальнейшее увеличение длины блока данных приводит к аппаратным сложностям).

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

Известен параллельный реконфигурируемый кодер БЧХ кодов (патент CN 101068113), в котором решена проблема параллельности для входного потока данных. Кодер рассчитан на ввод и вывод данных под настраиваемую ширину шины данных для аппаратной реализации в конкретном применении.

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

Известен параллельный реконфигурируемый кодер БЧХ кодов (патент CN 102761340), в котором решена проблема параллельности для входного потока данных. Кодер рассчитан на ввод и вывод данных под фиксированную ширину шины данных 8 бит.

Недостатком этого кодера является то, что в нем отсутствует способ построения схемы для настраиваемой ширины шины входных данных.

Известен параллельный реконфигурируемый кодер БЧХ кодов (патент CN 101227194), в котором решена проблема параллельности для входного потока данных. Кодер рассчитан на ввод и вывод данных под настраиваемую ширину шины данных для аппаратной реализации в конкретном применении.

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

Известен параллельный реконфигурируемый кодер БЧХ кодов (патент CN 102820892), в котором решена проблема параллельности для входного потока данных. Кодер рассчитан на ввод и вывод данных под настраиваемую ширину шины данных для аппаратной реализации в конкретном применении.

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

Наиболее близким к заявленному изобретению является кодер, описанный в патенте US 8,812,940 B2, в котором проблема настраиваемого кодера под различную корректирующую способность решена путем разбиения порождающего полинома на отдельные множители (по определению, порождающий полином состоит из произведения примитивных неприводимых полиномов). Кодирование осуществляют путем деления информационных бит на минимальные полиномы. В зависимости от применяемой корректирующей способности используют разные ответвления от общей цепи последовательно соединенных регистров с линейной обратной связью. Этот кодер выбран в качестве прототипа заявленного изобретения.

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

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

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

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

Фиг. 1. Функциональная схема кодера БЧХ кодов.

Фиг. 2. Функциональная схема параллельного кодера БЧХ кодов.

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

Фиг. 4. Структурная схема декодера БЧХ кодов.

Табл. 1. Пример заданных полиномов со степенями 10 и 8 в кодере согласно изобретению.

Рассмотрим кратко принцип функционирования кодера кодов БЧХ (Фиг. 1-2).

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

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

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

n - длина кодового слова (длина закодированных данных),

k - длина незакодированных данных,

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

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

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

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

Таким образом, данные на выходе кодера остаются неизменными, однако к ним добавляются контрольные данные r(x).

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

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

Для реализации выражения (2) применяют схему РЛОС, представленную на Фиг. 1. Первые k тактов работы кодера данные u(x) без изменений проходят на его выход и одновременно поступают на вход РЛОС. Переключатели P1, P2 находятся в положении I. В течение этого периода работы кодера происходит вычисление остатка r(x). После k тактов работы переключатели P1, P2 переходят в положение II, при этом они отключают петлю обратной связи и подключают РЛОС к выходу кодера. Последующие n-k тактов происходит выгрузка остатка r(x) из сдвигового регистра z₀, z₁, …, z_n-k-1. Перед началом кодирования очередного блока данных сдвиговые регистры z₀, z₁, …, z_n-k-1 сбрасывают в нулевое состояние. Тогда значения b₀, b₁, …, b_n-k-1, поступающие на вход регистров z₀, z₁, …, z_n-k-1 с выходов умножителей, можно описать с помощью следующего итеративного выражения:

где j - это позиция соответствующего умножителя g_j или сдвигового регистра z_j,

i - номер текущего такта работы схемы,

u_i - значение символа входных данных в текущем такте i.

В течение следующих (n-k) тактов схема РЛОС работает без обратной связи, просто как сдвиговый регистр, поэтому значения сигналов b₀, b₁, …, b_n-k-1 на входе сдвиговых регистров z₀, z₁, …, z_n-k-1 можно описать следующим образом:

Все операции выполняют в поле Галуа GF(p^m).

Вариант выполнения кодера с параллельным потоком данных представлен на Фиг. 2. Значения b_h,0, b_h,1, …, b_h,n-k-1 с выходов умножителей на каждой стадии, а именно на каждой параллельной ступени h потока данных u_h,i, можно представить следующим образом:

где u_h,i - значение h-го символа слова данных, поступивших в i-й такт.

Количество тактов работы кодера при этом уменьшается в L (размерность шины данных) раз с k до k/L, так как данные поступают параллельно. К моменту k/L такта данные заканчиваются, и вычисленные контрольные биты хранятся в сдвиговых регистрах z₀, z₁, …, z_n-k-1.

Данная схема значительно упрощается при кодировании двоичных кодов БЧХ. Для двоичных кодов БЧХ умножители в поле Галуа GF(p^m) в варианте выполнения кодера на Фиг. 2 заменяют простым элементом «И», сумматоры выполняют сложение по модулю 2, так как работают в поле Галуа GF(2^m), как показано в схеме на Фиг. 3, которая изображает вариант выполнения заявленного реконфигурируемого кодера БЧХ кодов. Настраиваемые регистры, хранящие коэффициенты g₀, g₁, …, g_n-k-1 порождающего полинома, являются одноразрядными. Алгоритм работы варианта выполнения заявленного кодера, представленный на Фиг. 3, аналогичен варианту в соответствии с Фиг. 2, но при этом заявленный кодер на Фиг. 3 становится реконфигурируемым. Заявленный кодер обладает настраиваемой корректирующей способностью за счет изменения состояния настраиваемых регистров g₀, g₁, …, g_n-k-1. При этом критический путь заявленного кодера немногим больше пути кодера без возможности реконфигурирования:

где τ_⊕ - задержка на элементе сумматора (исключающего «ИЛИ»),

τ_⊗ - задержка на элементе «И».

Критический путь в L раз больше пути в кодере последовательного потока данных (Фиг. 1), однако следует учитывать, что каждый такт на входе заявленного параллельного кодера (Фиг. 3) поступает L бит с шины данных.

Перед началом кодирования посредством заявленного кодера необходимо проинициализировать настраиваемые регистры, которые хранят значения коэффициентов g₀, g₁, …, g_n-k-1 порождающего полинома g(x). Так как порождающий полином можно задавать любой степени (от максимального количества значащих коэффициентов (n-k)_max до m), заявленный кодер является реконфигурируемым под требуемое количество исправляемых ошибок (от максимального до 1) для выбранного кода БЧХ. Для изменения требуемой корректирующей способности кода необходимо перед этапом кодирования перезаписать коэффициенты обновленного полинома. При этом необходимо учитывать, что значащий коэффициент при самой старшей степени полинома должен быть на месте настраиваемого регистра g_n-k-1, поэтому, если требуемый полином имеет степень меньшую, чем заложено в данной реализации (n-k)_max, необходимо обнулить настраиваемые регистры при младших степенях. В таблице 1 показан пример для случая, когда порождающие полиномы имеют степени 10 и в следующей строке степени 8. Коэффициент при старшей степени в кодах БЧХ всегда равен 1, поэтому в таблице он не приведен.

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

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

Заявленный реконфигурируемый кодер БЧХ кодов обладает следующими преимуществами:

- позволяет кодировать данные, поступающие с шины данных параллельно;

- позволяет кодировать данные кодом БЧХ с разной корректирующей способностью, то есть количеством исправляемых ошибок от t_max до 1;

- кодер двоичных кодов БЧХ позволяет применять его для разного расширения m поля Галуа - GF(2^m), что делает возможным использовать любые длины кодов n<2^m;

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

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

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

- может быть реализован в контроллере NAND-flash памяти, IP-блоке в составе СнК и др.

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

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

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

Изобретение относится к области цифровой обработки информации и может быть использовано для помехоустойчивого кодирования данных с переменной корректирующей способностью в различных системах передачи или приема, а также хранения данных. Техническим результатом является создание параллельного реконфигурируемого кодера БЧХ (Боуза - Чоудхури - Хоквингема) кодов, который позволяет кодировать под различные характеристики кодов БЧХ в процессе работы, позволяет настраивать корректирующую способность в зависимости от предназначения, а также позволяет обрабатывать данные, поступающие в кодер параллельно, с шины данных, и соответственно выдавать контрольные биты информации тоже в параллельном виде. Устройство содержит настраиваемые регистры, выполненные с возможностью хранения и выдачи коэффициентов порождающего полинома, сдвиговые регистры, выполненные с возможностью хранения и выдачи контрольных бит, и по меньшей мере две стадии, каждая из которых содержит сумматоры в поле Галуа и элементы «И». 1 табл., 4 ил.

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