Результат интеллектуальной деятельности: РЕКОНФИГУРИРУЕМЫЙ КОДЕР БЧХ КОДОВ

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

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

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

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

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

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

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

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

Поставленная задача решена путем создания реконфигурируемого кодера БЧХ кодов, содержащего соединенные между собой регистр с линейной обратной связью (РОЛС) и первый переключатель, причем вход кодера соединен с входом РОЛС и с первым входом первого переключателя, выход которого соединен с выходом кодера, а второй вход - с выходом РОЛС; при этом РОЛС включает в себя второй переключатель и, по меньшей мере, одну ветвь обратной связи, которая состоит из настраиваемого регистра, умножителя в поле Галуа, сдвигового регистра и сумматора в поле Галуа, причем настраиваемый регистр соединен с первым входом умножителя в поле Галуа, второй вход которого соединен с выходом второго переключателя, выход сдвигового регистра соединен с первым входом сумматора в поле Галуа, а выход сумматора в поле Галуа соединен с первым входом второго переключателя, второй вход сумматора в поле Галуа является входом РОЛС, а выход сдвигового регистра является также выходом РОЛС, причем настраиваемый регистр выполнен с возможностью инициализации перед началом кодирования, при этом записи коэффициента порождающего полинома, а также его хранения и передачи в умножитель в поле Галуа; в течение первых k тактов (k - длина входных незакодированных данных) работы кодера, при замкнутых первых входах первого и второго переключателей, при этом замкнутой ветви обратной связи и РОЛС, подключенном к входу кодера, входные незакодированные данные поступают с входа кодера на выход кодера через первый переключатель, а также на вход РОЛС, который выполнен с возможностью вычисления остатка от деления входных незакодированных данных на порождающий полином и записи остатка от деления в сдвиговый регистр в конце k-го такта после замыкания вторых входов первого и второго переключателей, при этом отключения ветви обратной связи; в течение следующих n-k тактов (n - длина кодового слова) работы кодера, при замкнутых вторых входах первого и второго переключателей, при этом разомкнутой ветви обратной связи и РОЛС, подключенном к выходу кодера, сдвиговый регистр выполнен с возможностью выгрузки на выход кодера контрольных бит входных данных в виде остатка от деления.

В предпочтительном варианте осуществления реконфигурируемый кодер БЧХ кодов содержит несколько ветвей обратной связи, каждая из которых состоит из настраиваемого регистра, умножителя в поле Галуа, сдвигового регистра и сумматора в поле Галуа; причем во всех ветвях обратной связи настраиваемый регистр соединен с первым входом умножителя в поле Галуа, второй вход которого соединен с выходом второго переключателя, а выход сдвигового регистра соединен с первым входом сумматора в поле Галуа; в первой ветви обратной связи выход умножителя в поле Галуа соединен с входом сдвигового регистра; во всех ветвях обратной связи, кроме последней, второй вход сумматора в поле Галуа соединен с выходом умножителя в поле Галуа последующей ветви обратной связи, а выход сумматора в поле Галуа соединен с входом сдвигового регистра последующей ветви обратной связи; в последней ветви обратной связи выход сумматора в поле Галуа соединен с первым входом второго переключателя, второй вход сумматора в поле Галуа является входом РОЛС, а выход сдвигового регистра является также выходом РОЛС, причем настраиваемый регистр выполнен с возможностью инициализации перед началом кодирования, при этом записи коэффициента порождающего полинома, а также его хранения и передачи в умножитель в поле Галуа; в течение первых k тактов (k - длина входных незакодированных данных) работы кодера, при замкнутых первых входах первого и второго переключателей, при этом замкнутой ветви обратной связи и РОЛС, подключенном к входу кодера, входные незакодированные данные поступают с входа кодера на выход кодера через первый переключатель, а также на вход РОЛС, который выполнен с возможностью вычисления остатка от деления входных незакодированных данных на порождающий полином и записи остатка от деления в сдвиговый регистр в конце k-го такта после замыкания вторых входов первого и второго переключателей, при этом отключения ветви обратной связи; в течение следующих n-k тактов (n - длина кодового слова) работы кодера, при замкнутых вторых входах первого и второго переключателей, при этом разомкнутой ветви обратной связи и РОЛС, подключенном к выходу кодера, сдвиговый регистр выполнен с возможностью выгрузки на выход кодера контрольных бит входных данных в виде остатка от деления.

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

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

Фиг. 1. Функциональная схема реконфигурируемого кодера систематического БЧХ кода согласно изобретению.

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

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

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

Элементы:

1 - первый переключатель;

2 - вход кодера;

3 - вход РОЛС (регистра с линейной обратной связью);

4 - выход кодера;

5 - второй переключатель;

6 - настраиваемый регистр;

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

8 - сдвиговый регистр;

9 - сумматор в поле Галуа.

Рассмотрим принцип функционирования заявленного реконфигурируемого кодера БЧХ кода.

В соответствии с определением кодов БЧХ, систематическое кодирование осуществляют согласно следующему выражению:

где m(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), что приводит к изменению схемы РОЛС. Схема РОЛС в заявленном изобретении выполнена с возможностью изменения порождающего полинома в процессе работы кодера с минимальными затратами его аппаратных ресурсов.

Рассмотрим более подробно вариант выполнения заявленного реконфигурируемого кодера БЧХ кода (Фиг. 1). Реконфигурируемый кодер БЧХ кодов содержит соединенные между собой регистр с линейной обратной связью (РОЛС) и первый переключатель 1. Вход 2 кодера соединен с входом 3 РОЛС и с первым входом первого переключателя 1, выход которого соединен с выходом 4 кодера, а второй вход - с выходом РОЛС. РОЛС включает в себя второй переключатель 5 и несколько ветвей обратной связи, которые образуют общую цепь обратной связи, и каждая из которых состоит из настраиваемого регистра 6, умножителя 7 в поле Галуа, сдвигового регистра 8 и сумматора 9 в поле Галуа. Во всех ветвях обратной связи настраиваемый регистр 6 соединен с первым входом умножителя 7 в поле Галуа, второй вход которого соединен с выходом второго переключателя 5, а выход сдвигового регистра 8 соединен с первым входом сумматора 9 в поле Галуа. В первой ветви обратной связи выход умножителя в поле Галуа соединен с входом сдвигового регистра. Во всех ветвях обратной связи, кроме последней, второй вход сумматора 9 в поле Галуа соединен с выходом умножителя 7 в поле Галуа последующей ветви обратной связи, а выход сумматора 9 в поле Галуа соединен с входом сдвигового регистра 8 последующей ветви обратной связи. В последней ветви обратной связи выход сумматора 9 в поле Галуа соединен с первым входом второго переключателя 5, второй вход сумматора 9 в поле Галуа является входом 3 РОЛС, а выход сдвигового регистра 8 является также выходом РОЛС.

Для реализации выражения (2) применяют схему РОЛС с настраиваемыми коэффициентами порождающего полинома и узлами управления. Перед началом кодирования инициализируют регистры 6, которые хранят значения коэффициентов g[0], g[1]…g[n-k-1] порождающего полинома g(x). В течение первых k тактов работы кодера данные m(x) без изменений проходят с входа 2 кодера на его выход 4 и одновременно поступают на вход 3 РОЛС. Первый и второй переключатели 1 и 5 при этом находятся в положении I. В течение этой первой фазы работы кодера вычисляют остаток r(x). После первых k тактов работы кодера первый и второй переключатели 1 и 5 переходят в положение II, при этом отключают петлю (цепь) обратной связи и подключают РОЛС к выходу 4 кодера. В течении последующих n-k тактов работы кодера выгружают остаток r(x) из сдвигового регистра 8 с[0], с[1], … c[n-k-1].

Арифметические операции в выражении (2), а также в варианте выполнения кодера на Фиг. 1 выполняют в расширенном (m - степень поля) поле Галуа GF(p^m). Поскольку порождающий полином можно задавать любой степени (от максимального количества значащих коэффициентов (n-k)_max до m), то кодер является реконфигурируемым под требуемое количество исправляемых ошибок (от максимального до 1) для выбранного кода БЧХ. Для изменения требуемой корректирующей способности кода, перед этапом кодирования перезаписывают коэффициенты обновленного полинома. При этом учитывают, что значащий коэффициент при самой старшей степени полинома должен быть на месте настраиваемого регистра 6 g[n-k-1] последней ветви обратной связи поэтому, если требуемый полином имеет степень меньшую, чем заложено в данной реализации (n-k)_max, тогда необходимо обнулить настраиваемые регистры 6 при младших степенях. В таблице 1 показаны примеры порождающих полиномов степеней 10 и 8. Коэффициент при старшей степени в кодах БЧХ всегда равен 1, поэтому в таблице он не приведен.

Наилучшее применение находит вариант выполнения заявленного кодера БЧХ кодов, предназначенный для кодирования двоичных кодов БЧХ (Фиг. 2). В этом варианте выполнения кодера умножители 7 в поле Галуа GF(p^m) выполнены в виде элементов «И» (Фиг. 2). Настраиваемые регистры 6, хранящие коэффициенты g[0], g[1]…g[n-k-1] порождающего полинома являются одноразрядными. Алгоритм работы этого варианта выполнения кодера (Фиг. 2) аналогичен описанному выше алгоритму работы первого варианта выполнения кодера (Фиг. 1).

В этом варианте выполнения кодера умножители 7 в поле Галуа выродились в простые элементы «И», при этом критический путь минимален, поэтому кодер обладает крайне высоким быстродействием, при этом аппаратные ресурсы немногим превосходят аналогичный кодер с фиксированными коэффициентами, без возможности реконфигурирования. Более того, в первом варианте выполнения кодера (Фиг. 1) умножители 7 выполнены в поле Галуа GF(p^m), это означает что максимальная длина кодового слова на выходе кодера ограничена n_max=p^m-1, и единственным параметром для реконфигурирования является количество исправляемых ошибок. Однако в схеме кодера на Фиг. 2 умножители 7 в поле Галуа вырождены в элементы «И», сумматоры 9 в поле Галуа выполняют сложение по модулю 2, так как работают в поле Галуа GF(2^m), и теоретически длина кодового слова на выходе не ограничена, потому как параметр m поля стал также настраиваемым. Максимальная степень полинома (количество настраиваемых регистров 6, хранящих коэффициенты в схеме кодера на Фиг. 2) ограничена, то есть m·t<(n-k)_max, где m - параметр поля, t - количество исправляемых ошибок. Таким образом, возможно и изменение расширения поля, и, как следствие, изменение максимальной длины кодового слова, и изменение корректирующей способности (количество исправляемых ошибок в кодовом слове).

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

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

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

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

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

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

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

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

- управление переключателями 1 и 5 кодера (Фиг. 1) предельно просто: первые k тактов загружают данные, потом переключают переключатели 1 и 5 в положении II и следующие n-k выгружают контрольные биты данных. Таким образом, управление кодером реализовано как для переменной длины данных, так и для переменного количества исправляемых ошибок;

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

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

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

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

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

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