×
12.04.2023
223.018.42f0

Результат интеллектуальной деятельности: Способ кодирования данных на основе LDPC кода

Вид РИД

Изобретение

№ охранного документа
0002743784
Дата охранного документа
26.02.2021
Аннотация: Изобретение относится к области кодирования информации с использованием кодов с низкой плотностью проверок на четность (LDPC) и предназначено для обеспечения работы немеханических запоминающих устройств на основе микросхем памяти. Технический результат - упрощение алгоритма вычисления кодового слова, обеспечивающего использование малого количества аппаратной логики. Способ кодирования данных на основе LDPC кода, в котором для генерирования кодового слова, состоящего из исходных данных и проверочных данных, используется проверочная матрица, которая содержит первую часть матрицы, относящуюся к исходным данным, и вторую часть матрицы, относящуюся к проверочным данным, при этом на главной диагонали второй части матрицы в нижней части располагаются циркулянты со сдвигом, равным нулю, а значения ячеек под главной диагональю второй части матрицы в этой же нижней части равны нулю.

Изобретение относится к устройствам кодирования информации с использованием кодов с низкой плотностью проверок на четность (LDPC) и предназначено для обеспечения работы немеханических запоминающих устройств на основе микросхем памяти (SSD, USB Flash Drive, Flash Card и т.д.), применяется в аппаратуре контроллера немеханических запоминающих устройств на основе микросхем памяти.

В контроллерах твердотельных дисков LDPC коды стали применятся относительно недавно, заменив доминирующие много лет в этой области БЧХ (Боуза-Чоудхури-Хоквингема) коды. Одной из основных причин замены кодов на LDPC стал массовый переход производителей твердотельных дисков от моделей флеш-памяти, где в одной ячейке памяти хранится один бит, к более экономичным видам памяти, где плотность информации значительно выше (два, три и более бит). С ростом числа исправляемых ошибок сложность LDPC декодеров растет линейно, что делает их более эффективными по площади и энергоэффективности, чем БЧХ декодеры. Дополнительным фактором в пользу выбора LDPC является высокая корректирующая способность: стандартный LDPC декодер (в отличие от БЧХ декодера), наряду с жёсткими решениями (‘0’ или ‘1’), получаемыми при чтении с носителя памяти, может использовать мягкие решения, представляющие собой вероятностные оценки (Log-Likelihood Ratio, LLR) для каждого бита хранимой информации, и получаемые путем чтения ячейки памяти с несколькими порогами чтения.

Недостатком применения LDPC кодов является большая аппаратная сложность для кодирования данных.

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

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

Применение такой проверочной матрицы позволит упростить процедуру кодирования.

Далее будет описано подробное осуществление изобретения.

Заявленный способ подразумевает использование LDPC кодера.

LDPC кодер кодирует поступающие данные блоками, также называемыми “кодовые слова”. Процесс кодирования заключается в добавлении к исходным данным некоторого количества дополнительных данных – проверочных данных, которые впоследствии используются декодером для проверки исправления ошибок. Таким образом, кодовое слово состоит из исходных данных — i и проверочных данных — p.

Конкретный LDPC код может быть задан несколькими способами, один из них — это проверочная матрица Н. Проверочная матрица двумерная, её длина равна длине кодового слова, если умножить эту матрицу на кодовое слово без ошибок, то получится нулевой вектор. Если же в кодовом слове есть ошибки, то получится ненулевой вектор s, называемый синдромом.

Исходя из того, что вектор синдромов должен быть равен нулю для кодового слова без ошибок, задача LDPC кодера состоит в построении проверочной части p на основе информационной части i и проверочной матрицы H.

Запишем условие равенства синдрома нулю в виде формулы:

H * (i, p) = s = 0

Разложим данное выражение в виде суммы:

H2 * i + H1 * p = 0

где H1 - часть проверочной матрицы, относящаяся к проверочным данным р, т.е. та часть матрицы Н, которая умножается на проверочные данные кодового слова для вычисления вектора матрицы;

а H2 – часть проверочной матрицы, относящаяся к исходным данным i, т.е. та часть матрицы Н, которая умножается на исходные данные кодового слова для вычисления вектора матрицы.

Перенесём одно слагаемое в правую часть и домножим обе части на H1-1, получим:

P = -H1-1 * H2 * i

Таким образом, вычисление проверочной части кодового слова сводится к двум умножениям вектора на матрицу.

Матрица H2 является низкоплотной, аппаратная реализация такого умножения достаточно проста, имеет низкую сложность и высокую скорость. Кроме того, обычно матрица H строится из ячеек (например, 128х128 или 512х512), каждая из которых либо содержит все нули, либо является единичной матрицей сдвинутой вправо на определённое количество позиций. Например, ячейка размера 4х4 сдвинутая на 1, будет выглядеть так:

Такие ячейки называют циркулянтами, а матрицы, состоящие из таких ячеек — квазициклическими. Умножение вектора на такую ячейку сводится к циклическому сдвигу всех элементов и имеет простую аппаратную реализацию.

Матрица H1-1, в свою очередь, является плотной матрицей, и умножение такой матрицы на вектор будет либо иметь большую аппаратную сложность, либо занимать длительное время. Для устранения этого недостатка матрица H1 строится таким образом, что в нижней части под главной диагональю расположены нули, а на диагонали расположены циркулянты со сдвигом, равным нулю.

Тогда для нижней строки (под строкой здесь будем понимать часть матрицы высотой равной размеру циркулянта) можно записать следующее условие равенства синдрома нулю:

где I — циркулянт с нулевым сдвигом, то есть единичная матрица, pn — блок проверочных бит с длиной, равной размеру циркулянта.

Таким образом, можно получить последний блок проверочных бит длины размера циркулянта без сложных вычислений: pn = – (H2 * i)n. Далее pn умножается на Cn и прибавляется к (H2 * i), тогда аналогично можно вычислить предпоследний блок проверочных бит:

pn–1 = – (H2 * i + Cn * pn)n–1

и так далее до:

pk = – (H2 * i + Ck+1..n * pk+1..n)k

Оставшаяся часть проверочных бит вычисляется умножением на обратную матрицу D–1, которая существенно меньше по размеру, чем H1–1:

p1..k–1 = – D–1 * (H2 * I + Ck..n * pk..n)1..k–1

Пример реализация способа

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

Первый модуль вычисляет вектор синдромов, умножая проверочную матрицу H на входные данные i, а затем на проверочные данные pn..pk по мере их вычисления. Результат помещается в блок памяти Memory.

Второй модуль умножает вектор синдромов из блока памяти Memory на обратную матрицу H–1.

Для повышения эффективности обработки входных данных первый модуль представлен в двух экземплярах. Так второй экземпляр первого модуля может начать обработку следующего кодового слова, не дожидаясь завершения обработки pn..pk первым экземпляром первого модуля. Затем эти экземпляры меняются ролями. Для реализации данного функционала память, хранящая ячейки проверочной матрицы, разделена на 2 части – memH2 и memCT.

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

В режиме чтения информационных данных первый модуль осуществляет умножение части LDPC-матрицы H2 на вектор входных данных i. Результатом умножения является вектор синдромов s, записанный в промежуточную память Memory.

Алгоритм работы модуля в данном режиме следующий:

a) на вход модуля поступает очередной блок входных данных размером с ячейку матрицы;

b) считывается конфигурация очередной ячейки матрицы H2 из памяти, извлекается информация о номере строки ячейки, сдвиге циркулянта и о том, является ли ячейка последней в столбце;

c) считывается текущее значение синдрома из промежуточной памяти Memory с адресом, равным номеру строки ячейки;

d) считанное значение синдрома суммируется с блоком входных данных, домноженным на сдвинутый циркулянт и записывается обратно в память Memory по тому же адресу;

e) если ячейка не последняя в столбце, то происходит переход к пункту b);

f) если блоки входных данных не кончились, то происходит переход к пункту a);

g) когда блоки входных данных кончились, модуль переходит в режим поочередного вычисления проверочных ячеек.

В режиме вычисления проверочных ячеек первый модуль осуществляет умножение части LDPC-матрицы Ck..n на блоки проверочных бит pn..pk по мере их вычисления. Алгоритм работы отличается от режима работы при чтении исходных данных только тем, что первый модуль выдает текущее значение одной из ячеек синдрома по запросу LDPC-кодера, которое затем направляется на вход первого модуля, т.к. оно и является очередным вычисленным блоком проверочных бит.

Второй модуль осуществляет умножение вектора синдромов, посчитанного первым, на плотную матрицу Н-1 и работает по следующему алгоритму:

a) считывается очередной блок синдромов размера cell_size из промежуточной памяти Memory;

b) считывается часть столбца матрицы Н-1 из памяти, хранящая ячейки проверочной матрицы;

c) производится умножение считанной части столбца на rwidth бит блока синдромов, результат добавляется к соответствующей ячейке промежуточной памяти Memory;

d) если биты синдромов не закончились, то происходит переход к пункту b);

e) если столбцы не закончились, происходит переход к пункту a);

f) когда все столбцы обработаны, результаты из промежуточной памяти Memory подаются на выход;

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

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

Showing 1-10 of 11 items.
26.12.2018
№218.016.aafa

Способ обнаружения оставленного предмета в видеопотоке

Изобретение относится к средствам автоматического анализа видеопотока. Технический результат заключается в повышении качества обнаружения объектов. В способе: обеспечивают поток изображений наблюдаемого пространства, содержащий последовательность растровых кадров; формируют статистику...
Тип: Изобретение
Номер охранного документа: 0002676028
Дата охранного документа: 25.12.2018
26.12.2018
№218.016.ab04

Способ анализа видеопотока

Изобретение относится к средствам обработки растровых изображений. Технический результат заключается в повышении точности определения подвижных объектов. В способе: получают первый кадр видеопотока, для каждого пикселя которого определяют значение следующих компонент: компоненты Y яркости,...
Тип: Изобретение
Номер охранного документа: 0002676026
Дата охранного документа: 25.12.2018
26.12.2018
№218.016.ab17

Способ идентификации объекта в видеопотоке

Изобретение относится к способам автоматического анализа видеопотока. Технический результат заключается в повышении качества идентификации объекта. Предложен способ анализа видеопотока, состоящий в том, что обеспечивают поток изображений наблюдаемого пространства, содержащий последовательность...
Тип: Изобретение
Номер охранного документа: 0002676029
Дата охранного документа: 25.12.2018
13.01.2019
№219.016.aef9

Способ обработки видеопотока в системе видеонаблюдения

Изобретение относится к средствам видеонаблюдения. Технический результат заключается в повышении качества обработки водеопотока. Способ обработки видеопотока в системе видеонаблюдения, состоящий в том, что обеспечивают, по крайней мере, один программируемый микросервер на базе аппаратной...
Тип: Изобретение
Номер охранного документа: 0002676950
Дата охранного документа: 11.01.2019
12.04.2023
№223.018.427a

Устройство мониторинга и контроля обращений к bios со стороны цп

Изобретение относится к области вычислительной техники. Техническим результатом является повышение безопасности системы, мониторинг и контроль модификации BIOS. Устройство мониторинга и контроля обращений к BIOS со стороны центрального процессора (ЦП) включает независимый модуль контроля...
Тип: Изобретение
Номер охранного документа: 0002762519
Дата охранного документа: 21.12.2021
12.04.2023
№223.018.429e

Способ записи секторных данных в кэш-память

Изобретение относится к вычислительной технике. Технический результат заключается в повышении эффективности использования твердотельного накопителя информации (ТНИ) путем оперативного считывания секторных данных, хранящихся в контроллере ТНИ. Способ записи секторных данных в кэш-память...
Тип: Изобретение
Номер охранного документа: 0002752782
Дата охранного документа: 03.08.2021
12.04.2023
№223.018.42a3

Способ шифрования данных

Изобретение относится к компьютерной технике и предназначено для шифрования данных на носителях информации. Технический результат заключается в упрощении шифрование данных с сохранением надежности их защиты. Технический результат достигается за счет того, что шифрование осуществляется...
Тип: Изобретение
Номер охранного документа: 0002759862
Дата охранного документа: 18.11.2021
12.04.2023
№223.018.42c7

Способ записи страничных данных в кэш-память

Изобретение относится к вычислительной технике. Технический результат заключается в увеличении производительности работы компьютера путем оперативного доступа к часто используемым данным. Способ записи страничных данных в кэш-память твердотельного накопителя информации (ТНИ) содержит этапы, на...
Тип: Изобретение
Номер охранного документа: 0002750132
Дата охранного документа: 22.06.2021
12.04.2023
№223.018.42ce

Способ измерения скоростных характеристик запоминающего устройства

Изобретение относится к компьютерной технике и предназначено для измерения скоростных характеристик различных периферийных устройств, осуществляющих запись и хранение информации, устанавливаемых на вычислительные системы. Техническим результатом является обеспечение возможности измерения...
Тип: Изобретение
Номер охранного документа: 0002754960
Дата охранного документа: 08.09.2021
12.04.2023
№223.018.42cf

Способ инкрементального сохранения

Изобретение относится к области компьютерной техники и предназначено для обеспечения корректности работы немеханических запоминающих устройств на основе микросхем памяти. Техническим результатом является уменьшение объема памяти для хранения данных секторов и сокращение времени сохранения таких...
Тип: Изобретение
Номер охранного документа: 0002754601
Дата охранного документа: 03.09.2021
Showing 1-10 of 21 items.
10.01.2015
№216.013.18f2

Способ запуска гипервизора в компьютерной системе на ранней стадии загрузки компьютера

Изобретение относится к области запуска гипервизора в компьютерной системе на ранней стадии загрузки компьютера. Техническим результатом является повышение безопасности компьютера. Способ запуска гипервизора в компьютерной системе на ранней стадии загрузки компьютера заключается в загрузке...
Тип: Изобретение
Номер охранного документа: 0002537814
Дата охранного документа: 10.01.2015
10.01.2015
№216.013.1aca

Способ запуска гипервизора в компьютерной системе на ранней стадии загрузки компьютера

Изобретение относится к области запуска гипервизора в компьютерной системе на ранней стадии загрузки компьютера. Техническим результатом является повышение безопасности компьютера. Способ запуска гипервизора в компьютерной системе на ранней стадии загрузки компьютера заключается в загрузке...
Тип: Изобретение
Номер охранного документа: 0002538286
Дата охранного документа: 10.01.2015
27.11.2015
№216.013.9446

Устройство создания доверенной среды для компьютеров специального назначения

Изобретение относится к информационной безопасности. Технический результат заключается в повышении эффективности защиты от несанкционированного доступа (НСД) к аппаратным и программным компонентам и к информации, хранимой и обрабатываемой в ПК. Устройство создания доверенной среды и защиты...
Тип: Изобретение
Номер охранного документа: 0002569577
Дата охранного документа: 27.11.2015
27.03.2016
№216.014.c814

Устройство для приёма сигнала из рельсовой цепи

Изобретение относится к области железнодорожной автоматики и телемеханики. Устройство содержит блок приема амплитудно-модулированного сигнала, вход которого соединен с входами блока нелинейной обработки сигнала и блока спектральной обработки сигнала, выход блока нелинейной обработки и выход...
Тип: Изобретение
Номер охранного документа: 0002578899
Дата охранного документа: 27.03.2016
26.12.2018
№218.016.aafa

Способ обнаружения оставленного предмета в видеопотоке

Изобретение относится к средствам автоматического анализа видеопотока. Технический результат заключается в повышении качества обнаружения объектов. В способе: обеспечивают поток изображений наблюдаемого пространства, содержащий последовательность растровых кадров; формируют статистику...
Тип: Изобретение
Номер охранного документа: 0002676028
Дата охранного документа: 25.12.2018
26.12.2018
№218.016.ab04

Способ анализа видеопотока

Изобретение относится к средствам обработки растровых изображений. Технический результат заключается в повышении точности определения подвижных объектов. В способе: получают первый кадр видеопотока, для каждого пикселя которого определяют значение следующих компонент: компоненты Y яркости,...
Тип: Изобретение
Номер охранного документа: 0002676026
Дата охранного документа: 25.12.2018
26.12.2018
№218.016.ab17

Способ идентификации объекта в видеопотоке

Изобретение относится к способам автоматического анализа видеопотока. Технический результат заключается в повышении качества идентификации объекта. Предложен способ анализа видеопотока, состоящий в том, что обеспечивают поток изображений наблюдаемого пространства, содержащий последовательность...
Тип: Изобретение
Номер охранного документа: 0002676029
Дата охранного документа: 25.12.2018
13.01.2019
№219.016.aef9

Способ обработки видеопотока в системе видеонаблюдения

Изобретение относится к средствам видеонаблюдения. Технический результат заключается в повышении качества обработки водеопотока. Способ обработки видеопотока в системе видеонаблюдения, состоящий в том, что обеспечивают, по крайней мере, один программируемый микросервер на базе аппаратной...
Тип: Изобретение
Номер охранного документа: 0002676950
Дата охранного документа: 11.01.2019
29.04.2019
№219.017.4449

Устройство для приема сигнала из рельсовой цепи

Изобретение относится к области железнодорожной автоматики и может быть использовано в устройствах сигнализации, централизации и блокировки на железнодорожном транспорте, в частности в устройствах интервального регулирования движения поездов на перегонах и станциях. Устройство содержит блок...
Тип: Изобретение
Номер охранного документа: 0002453460
Дата охранного документа: 20.06.2012
29.06.2019
№219.017.9fa5

Устройство для передачи сигнала в рельсовую цепь

Изобретение относится к области железнодорожной автоматики и может быть использовано в устройствах сигнализации, централизации и блокировки на железнодорожном транспорте, в частности, в устройствах интервального регулирования движения поездов на перегонах и станциях. Устройство содержит...
Тип: Изобретение
Номер охранного документа: 0002453461
Дата охранного документа: 20.06.2012
+ добавить свой РИД