Актуальные проблемы современной науки: тезисы докладов ХХVІ Международной научно-практической конференции (Санкт-Петербург – Астана – Киев – Вена, 30 января 2018)
Секция: Технические науки
Сайлаукызы Жулдыз
докторант кафедры «Вычислительная техника»
Евразийского национального университета
имени Л. Н. Гумилева
г. Астана, Республика Казахстан
ОБЕСПЕЧЕНИЕ НАДЁЖНОГО ХРАНЕНИЯ ДАННЫХ ВО FLASH-ПАМЯТИ
Введение. Flash-память благодаря компактности, дешевизне, механической прочности, большому объёму, скорости работы и низкому энергопотреблению, широко используется в цифровых портативных устройствах и носителях информации. Повышение плотности записи, достигаемое за счет уменьшающегося физического размера ячейки наряду с возрастающим количеством используемых состояний, приводит к снижению надежности хранения данных, что требует использования помехоустойчивого кодирования.
Обеспечение надёжного хранения данных в больших объёмах флеш-памяти также становится всё более актуальной. При быстром увеличении объёма таких блоков хранения данных и значительным росте требований к целостности хранимой в них информации методы решения этой проблемы до не давнего времени практически не развивались. Но эта задача становится всё более актуальной, поскольку даже редкие ошибки при передаче критически важной информации во многих случаях вообще недопустимы.
К настоящему времени предложено довольно много вариантов помехоустойчивого кодирования, предназначенного для многоуровневой NAND flash-памяти: коды БЧХ, коды Рида - Соломона, низкоплотностные коды (LDPC), решетчатые коды [1, с. 241-249; 2, с. 429-439; 3, с. 900-908]. Очень важно, что требуемая вероятность ошибки на бит в данном случае должна быть очень малой, порядка 10-12 ÷10-15.
Коды с низкой плотностью проверок на четность (LDPC) показывают хорошие практические результаты при использовании вероятностного декодирования [4, с. 144].
LDPC-код задается своей проверочной матрицей Н, обладающей свойством разреженности, т.е. строки и столбцы матрицы содержат мало ненулевых позиций по сравнению с ее размерностью.
LDPC код представляется графом Таннера [5, с. 721-727; 6, с. 766-775] (рис.1). Узлы в графе Таннера называются информационными и проверочными узлами, которые мы обозначим как C и F, соответственно. Можно отметить, что граф будет содержать f проверочных узлов F, по одному для каждого проверочного уравнения, и C информационных узлов c, по одному для каждого символа кодового слова.
Рис. 1. Граф Таннера для линейного блокового кода (8, 16)
С целью анализа эффективности реализации рассмотрим основные алгоритмы декодирования LDPC кодов. LDPC код – это частный случай линейного блочного кода. В этом кодировании мы будем использовать две матрицы: одна является генераторной матрицей G на кодировщике и матрица проверки на четность H на декодере. Кодирование линейного блочного (n, k) – кода задается генераторной матрицей Gn,k, которая определяется как массив размером kп.
Генерация кодового слова U в матричной записи равна произведению:
(1)
(8, 16) - коде генераторная матрица (G) и проверочная матрица (H) имеют следующий вид:
Рассмотрим кодирование информационных символов [u=01001110]
(2)
Декодирование. Bit-flipping алгоритм является жестким методом декодирования сообщений для LDPC-кодов. В канал связи с шумами поступает сообщение с кодовым словом y=01001010 00110011, если проверить его на принадлежность к кодовым словам то результат отличен от нуля, а следовательно вектор «у» не является кодовым словом, а это значит, что во время передачи возникли ошибки. Производится инициализация и на бит-узлы поступают значения с входа декодера. На первом шаге проверочные узлы считывают значения с бит-узлов и формируют сообщения для второго шага. На втором шаге проверочные узлы отправляют значения на бит-узлы для сравнения.
Таблица 1
Алгоритм инверсии битов (bit-flipping algorithm)
Последний шаг запускает проверку нового сообщения на соответствие проверочным уравнениям матрицы H. Для 0-7 узла.
f0= y8=0
f1= y2 Åy3 Åy4 Åy6Åy7 Åy9=0
f2= y2 Åy3 Åy4 Åy7 Åy10=0
f3= y2Åy4 Åy11=0
f4= y1 Åy5 Åy7 Åy12=0
f5= y0Åy1 Åy2 Åy3 Åy4 Åy5 Åy6 Åy13=0=0
f6= y0 Åy3 Åy4 Åy14=0
f7= y0Åy1 Åy3 Åy4 Åy6 Åy15=0
В результате проверки не было найдено несоответствий, поэтому алгоритм останавливается и возвращает. 01001110 00110011.
Реализация программного модуля кодирования и декодирования на основе математических моделей и алгоритмов. Языком описания был выбран Verilog HDL, наиболее часто используемый в проектировании, верификации и реализации аналоговых, цифровых и смешанных электронных систем на различных уровнях абстракции. Была выбрана среда проектирования Vivado, поддерживающая разработку программного обеспечения.
Структурная схема разработанной системы, включающей кодер и декодер приведена на рисунке 2. Кодер включает в себя: сдвигающий регистр и логические элементы сложения по модулю два, осуществляющие формирование проверочных символов.
Рис. 2. Структурная схема аппаратного блока включающей кодер и декодер
Таким образом, применение корректирующих кодов позволяет обнаружить, и по возможности исправить искаженные данные, причем ранее записанные данные и их структура останутся в неприкосновенности.
Литература
