Декодер кода боуза-чоудхури-хоквингема с каноническим декодером хэмминга
Владельцы патента RU 2704499:
Федеральное государственное автономное образовательное учреждение высшего образования "Санкт-Петербургский государственный университет аэрокосмического приборостроения" (RU)
Изобретение относится к области помехоустойчивого кодирования и может быть использовано для повышения качества связи и надежности хранения данных в микросхемах памяти. Технический результат заключается в повышении эффективности декодирования БЧХ кода с кодовым расстоянием 5 и 6. Декодер кода Боуза-Чоудхури-Хоквингема с каноническим декодером Хэмминга содержит: блок перестановки, подключенный к блоку вычисления позиции ошибки в каноническом коде Хэмминга и блоку вычисления синдрома. Блок вычисления позиции ошибки в каноническом коде Хэмминга, блок вычисления обратного элемента в третьей степени, первый блок умножения, блок решения ключевого уравнения и второй блок умножения подключены последовательно. На второй вход второго блока умножения подключен блок вычисления позиции ошибки в каноническом коде Хэмминга. Второй блок умножения подключен к первому блоку суммирования и первому дешифратору. К первому блоку суммирования подключены блок вычисления позиции ошибки в каноническом коде Хэмминга и второй дешифратор. Первый дешифратор, второй дешифратор и блок перестановки подключены ко второму блоку суммирования, который подключен к блоку обратной перестановки. 2 з.п. ф-лы, 2 ил.
Изобретение относится к области помехоустойчивого кодирования и может быть использовано для повышения качества связи и надежности хранения данных в микросхемах памяти.
Известен быстрый программный Боуза-Чоудхури-Хоквингема (далее - БЧХ) кодер и декодер (URL: http://www.channelscience.com/files/NealGloverFastSoftwareBCHEndecR400r2.pdf), который включает в себя блок вычисления синдрома, блок составления ключевого уравнения и блок прямого решения ключевого уравнения.
Недостатком данного декодера является повышенная сложность реализации, вызванная необходимостью хранения таблицы логарифмов в дополнительном блоке памяти.
Известно декодирование двойных ошибок и обнаружение тройных ошибок при помощи БЧХ кодов (заявка № US 4556977 A, опубл. 15.09.1983, URL: https://patents.google.com/patent/US4556977A), которое включает вычислитель синдрома, генератор коэффициента для каждого бита кодового слова и детектор нуля.
Недостатком данного аналога является повышенная сложность реализации, так как необходимо для каждого бита кодового слова вычислять определенный коэффициент, который равен произведению верхней половины синдрома на соответствующую данному биту матрицу.
Известен БЧХ декодер (заявка № US 8806308 B2, опубл. 12.08.2014, URL: https://www.google.com/patents/US8806308), который состоит из генератора синдрома, блока решения ключевого уравнения и блока нахождения позиции ошибки по локатору.
Недостатком данного аналога является необходимость использования блока вычисления ошибки по синдрому, что влечет за собой дополнительные временные и аппаратные затраты.
Наиболее близким техническим решением является "Прямой табличный декодер, исправляющий две ошибки в БЧХ коде и использующий пару синдромов" (заявка № US 4030067 A, опубл. 29.12.1975, URL: https://patents.google.com/patent/US4030067A).
Прямой табличный декодер состоит из первого блока умножения, на входы которого подключены шины от блока вычисления синдрома, вход которого подключен к первой шине, и блока вычисления обратного элемента в третьей степени, вход которого подключен к шине S1, а выход первого блока умножения через шину с инвертором нулевого бита подключен к входу блока решения ключевого уравнения, выход которого подключен на вход второго блока умножения, на второй вход которого подключена шина S1, а его выход подключен к первому дешифратору и первому блоку суммирования, на второй вход которого подключена шина S1, а выход подключен к входу второго дешифратора, выходы дешифраторов и первая шина подключены ко второму блоку суммирования, шина S1 и шина S3 подключены на входы блока флагов.
Прямой табличный декодер работает следующим образом: входное слово подается на блок вычисления синдрома на выходе которого формируется первая и вторая компоненты синдрома. Первая компонента синдрома подается на блок вычисления обратного элемента в третьей степени. Первый блок умножения перемножает результат работы блока вычисления обратного элемента в третьей степени со второй компонентой синдрома и подает результат через шину с инвертором нулевого бита на блок решения ключевого уравнения. Выход которого подается на вход второго блока умножения, на второй вход которого подается первая компонента синдрома. На выходе второго блока умножения появляется первый локатор ошибки, который поступает на первый дешифратор. Первый дешифратор по таблице преобразует первый локатор в вектор первой ошибки и подает его на второй блок суммирования. Также выход второго блока умножения подается на первый блок суммирования, на выходе которого образуется второй локатор, который подается на второй дешифратор. Выход второго дешифратора подается на второй блок суммирования, который производит сумму входного слова с двумя векторами ошибок и выдает на шину выхода исправленное кодовое слово.
Недостатком прототипа является повышенная сложность реализации, вызванная тем, что из-за структуры блока вычислителя синдрома для нахождения позиции ошибки необходимо использовать таблицу в первом дешифраторе и втором дешифраторе, а также необходимо хранить таблицу для решения ключевого уравнения.
Задачей создания изобретения является разработка декодера помехоустойчивого кода, который позволял бы исправлять одиночные и двойные ошибки, а также обнаруживать тройные ошибки и при этом имел бы минимальную аппаратную сложность при высокой скорости работы.
Техническим результатом является уменьшение аппаратной сложности декодера произвольного БЧХ кода с кодовым расстоянием 5 и 6.
Технический результат достигается тем, что в декодер, содержащий: первый блок умножения, на входы которого подключены шины от блока вычисления синдрома, вход которого подключен к первой шине, и блока вычисления обратного элемента в третьей степени, вход которого подключен к шине S1, а выход первого блока умножения через шину с инвертором нулевого бита подключен к входу блока решения ключевого уравнения, выход которого подключен на вход второго блока умножения, на второй вход которого подключена шина S1, а его выход подключен к первому дешифратору и первому блоку суммирования, на второй вход которого подключена шина S1, а выход - подключен к входу второго дешифратора, выходы дешифраторов и первая шина подключены ко второму блоку суммирования, шина S1 и шина S3 подключены на входы блока флагов, дополнительно установлены блок перестановки, подключенный к шине входа и первой шине, блок обратной перестановки, подключенный к выходу второго блока суммирования и шине выхода, блок вычисления ошибки в каноническом коде Хэмминга, вход которого подключен к первой шине, а выход к шине S1, блок проверки на четность, вход которого подключен к первой шине, а выход к блоку флагов, причем первый и второй дешифраторы выполнены на высокоскоростных аппаратных демультиплексорах, блок перестановки и блок обратной перестановки выполнены перемежением проводников, блок вычисления ключевого уравнения выполнен на аппаратной схеме вычисления следа в поле Галуа, а блок флагов выполнен на аппаратной схеме, обнаруживающей одиночные, двойные, тройные ошибки.
Технический результат достигается за счет введения дополнительных блоков и связей, а именно блока перестановки, установленного между шиной входа и первой шиной, блока вычисления позиции ошибки в каноническом коде Хэмминга, установленного между первой шиной и шиной S1, блока проверки на четность, на вход которого подключен выход блока перестановки, а выход которого подключен к блоку флагов и блока обратной перестановки, подключенного между выходом второго блока суммирования и шиной выхода, которые позволяют дать причинно-следственную связь между введением новых блоков (связей) и техническим результатом. Выполненные изменения позволяют понизить требования к сложности аппаратной реализации декодера БЧХ кода и увеличить скорость его работы, так как дают возможность упростить и ускорить первый и второй дешифраторы.
Сущность изобретения поясняется чертежами, где на фиг. 1 представлена схема декодера, на фиг 2. представлена схема блока вычисления позиции ошибки в каноническом коде Хэмминга и введены следующие обозначения:
n - длина кодового слова
r - количество проверочных символов
1 - Блок перестановки
2 - Блок вычисления позиции ошибки в каноническом коде Хэмминга
3 - Блок вычисления синдрома
4 - Блок проверки на четность
5 - Блок вычисления обратного элемента в третьей степени
6 - Первый блок умножения
7 - Блок флагов
8 - Блок решения ключевого уравнения
9 - Второй блок умножения
10 - Первый блок суммирования
11 - Первый дешифратор
12 - Второй дешифратор
13 - Второй блок суммирования
14 - Блок обратной перестановки
Декодер кода Боуза-Чоудхури-Хоквингема с каноническим декодером Хэмминга содержит: блок перестановки 1, на вход которого подключена шина входа, а выход подключен к входу блока вычисления позиции ошибки в каноническом коде Хэмминга 2, входу блока вычисления синдрома 3, входу блока проверки на четность 4. Выход блока вычисления позиции ошибки в каноническом коде Хэмминга 2 подключен ко входу блока вычисления обратного элемента в третьей степени 5, выход которого подключен к первому блоку умножения 6, выход которого через шину с инвертором нулевого бита подключен к входу блока флагов 7, на вход которому также подключены выход блока вычисления ошибки в каноническом коде Хэмминга 2, блок вычисления синдрома 3 и блок проверки на четность 4. Выход первого блока умножения 6 через шину с инвертором подключен ко входу блока решения ключевого уравнения 8, выход которого подключен ко второму блоку умножения 9, на второй вход которого подключен выход блока вычисления позиции ошибки в каноническом коде Хэмминга 2. Выход второго блока умножения 9 подключен ко второму входу первого блока суммирования 10 и первому дешифратору 11. Ко второму входу первого блока суммирования 10 подключен выход блока вычисления позиции ошибки в каноническом коде Хэмминга 2. Выход первого блока суммирования 10 подключен к входу второго дешифратора 12. Выходы первого дешифратора 11, второго дешифратора 12 и блока перестановки 1 подключены ко входам второго блока суммирования 13, выход которого подключен к блоку обратной перестановки 14, выход которого подключен к шине выхода.
Блок перестановки 1 выполнен, например, на проводниках, соединение которых между входом и выходом блока выполнены таким образом, чтобы привести систематический вид входного кодового слова к лексикографическому виду.
Блок вычисления позиции ошибки в каноническом коде Хэмминга 2 выполнен, например, на шифраторе, построенном на аппаратных элементах сложения по модулю два [1, 2, 3].
Блок вычисления синдрома 3 выполнен, например, на элементах сложения по модулю 2 [4].
Блок проверки на четность 4 выполнен, например, на нескольких сумматорах типа "исключающего ИЛИ".
Блок вычисления обратного элемента в третьей степени 5 выполнен, например, на заранее рассчитанной таблице.
Первый блок умножения 6 выполнен, например, на элементах "И" и сложения по модулю 2 [5].
Блок флагов 7 выполнен, например, на аппаратной схеме из компонентов "ИЛИ", "И", "НЕ".
Блок решения ключевого уравнения 8 выполнен, например, на аппаратной схеме, использующей результат вычисления следа элементов в поле Галуа. [6].
Второй блок умножения 9 выполнен, например, на элементах "И" и элементах сложения по модулю 2 [5].
Первый блок суммирования 10 выполнен, например, на элементах сложения по модулю два с двумя входами.
Первый дешифратор 11 и второй дешифратор 12 выполнены на высокоскоростных аппаратных демультиплексорах [7].
Первый блок суммирования 13 выполнен, например, на элементах сложения по модулю два с тремя входами.
Блок перестановки 14 выполнен, например, на проводниках, соединение которых между входом и выходом блока выполнены таким образом, чтобы произвести перестановку символов кодового слова таким образом, чтобы первая часть синдрома соответствовала каноническому декодеру кода Хэмминга.
Декодер кода Боуза-Чоудхури-Хоквингема с каноническим декодером Хэмминга работает следующим образом: входное слово подается на вход блока перестановки 1, который осуществляет перестановку бит входного кодового слова таким образом, чтобы оно соответствовало лексикографическому виду кода. Выходные биты блока перестановки 1 поступают на вход блока вычисления позиции ошибки в каноническом коде Хэмминга 2, который вычисляет первую компоненту синдрома кода Боуза-Чоудхури-Хоквингема, которая соответствует позиции ошибочного бита в случае, если произошла одна ошибка. Также выходные биты блока перестановки 1 поступают на вход блока вычисления синдрома 3, результатом работы которого является вторая компонента синдрома. Первая компонента синдрома подается на блок вычисления обратного элемента в третьей степени 5, результат которого подается на первый блок умножения 6. Также на первый блок умножения 6 подается вторая компонента синдрома, в результате чего на выходе первого блока умножения 6 получаем отношение второй компоненты синдрома к первой компоненте синдрома в третьей степени. Далее к результату первого блока умножения 6 прибавляется единица при помощи шины с инвертором нулевого бита, результат поступает на блок решения ключевого уравнения 8, на выходе которого появляется один корень уравнения. Корень ключевого уравнения перемножается с первой компонентой синдрома при помощи второго блока умножения 9 в результате чего на выходе второго блока умножения 9 оказывается вектор, двоичным представление которого является порядковый номер первого ошибочного бита. Для вычисления порядкового номера второго ошибочного бита результат второго блока умножения 9 складывается с первой компонентой синдрома при помощи первого блока суммирования 10. Порядковый номер первого ошибочного бита подается на вход первого дешифратора 11, а порядковый номер второго ошибочного бита подается на вход второго дешифратора 12. Выходом первого дешифратора 11 является вектор, у которого единица на позиции первого ошибочного бита, а все остальные нули. Выходом второго дешифратора 12 является вектор, у которого единица на позиции второго ошибочного бита, а все остальные нули. Выходные значения дешифраторов подаются на входы второму блоку суммирования 13, на который также поступают биты, полученные с выхода блока перестановки 1. На выходе второго блока суммирования 13 оказывается исправленное кодовое слово кода, имеющего лексикографически упорядоченную верхнюю половину проверочной матрицы. Для приведения полученного от второго блока суммирования 13 кодового слова к исходному коду это слово подается на вход блока обратной перестановки 14, результатом работы которого является исправленное кодовое слово исходного систематического кода. Параллельно с этим осуществляется установка состояния флагов, указывающих на то, насколько далеко находится принятое слово от кодовых слов. Это осуществляется при помощи блока флагов 7, на вход которому поданы две компоненты синдрома, вектор на выходе шины с инвертором нулевого бита и выход блока проверки на четность 4, на вход которого подаются биты с выхода блока перестановки 1.
На основании вышесказанного можно сделать вывод, что предлагаемое изобретение позволяет реализовать декодеры для целого класса БЧХ кодов исправляющих двойные и обнаруживающих тройные ошибки, причем при декодировании не используется операция логарифмирования и необходимая для этого таблица, а достаточно двух быстрых аппаратных демультиплексоров, что значительно экономит аппаратные средства и повышает скорость работы кодировочной системы.
Используемая литература:
1. Мак-Вильямс Ф., Слоэн Н. Теория кодов, исправляющих ошибки Пер. с англ. - М.: Связь, 1979. - 744 с. (раздел 1.7, стр. 33-34)
2. Аршинов М.Н., Садовский Л.Е. 'Коды и математика (рассказы о кодировании)' \\ Библиотечка 'Квант'. Выпуск 30 - Москва: Наука, 1983 - с. 144 (стр. 45-47)
3. R.W. Hamming, Error detecting and error correcting codes - The Bell system technical journal - Volume 29, Number 2, April 1950 (pages 147-160)
4. Титце У., Шенк К. Полупроводниковая схемотехника. 12-е изд. Том I: Пер. с нем. - М.: ДМК Пресс, 2008. - 832 с.: ил. ISBN 5-94074-148-7 (раздел 8.6 стр. 734)
5. Рахман П.А. Арифметика двоичного поля Галуа на базе быстрого умножения и инвертирования элементов поля и ее аппаратная реализация // Международный журнал прикладных и фундаментальных исследований. - 2015. - №12-3. - С. 403-408;
6. Э. Берлекэмп Алгебраическая теория кодирования, Изд. МИР, 1971. - 477 с. (глава 11, 252 стр.)
7. Титце У., Шенк К. Полупроводниковая схемотехника. 12-е изд. Том I: Пер. с нем. - М.: ДМК Пресс, 2008. - 832 с.: ил. ISBN 5-94074-148-7 (раздел 8.2.2 стр. 727)
1. Декодер кода Боуза-Чоудхури-Хоквингема с каноническим декодером Хэмминга, содержащий первый блок умножения, на входы которого подключены шины от блока вычисления синдрома, вход которого подключен к первой шине, и блока вычисления обратного элемента в третьей степени, вход которого подключен к шине S1, а выход первого блока умножения через шину с инвертором нулевого бита подключен к входу блока решения ключевого уравнения, выход которого подключен на вход второго блока умножения, на второй вход которого подключена шина S1, а его выход подключен к первому дешифратору и первому блоку суммирования, на второй вход которого подключена шина S1, а выход подключен к входу второго дешифратора, выходы дешифраторов и первая шина подключены ко второму блоку суммирования, шина S1 и шина S3 подключены на входы блока флагов, отличающийся тем, что дополнительно установлены блок перестановки, подключенный к шине входа и первой шине, блок обратной перестановки, подключенный к выходу второго блока суммирования и шине выхода, блок вычисления ошибки в каноническом коде Хэмминга, вход которого подключен к первой шине, а выход - к шине S1, блок проверки на четность, вход которого подключен к первой шине, а выход - к блоку флагов.
2. Декодер кода Боуза-Чоудхури-Хоквингема с каноническим декодером Хэмминга по п. 1, отличающийся тем, что первый и второй дешифраторы выполнены, например, на высокоскоростных аппаратных демультиплексорах.
3. Декодер кода Боуза-Чоудхури-Хоквингема с каноническим декодером Хэмминга по п. 1, отличающийся тем, что блок перестановки и блок обратной перестановки выполнены перемежением проводников.
