Предыстория

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

В далеком 2017 году мне передали SD-карту памяти с диагнозом «сломана пополам, вдруг получится что-то с нее считать». Я честно пробовал: восстановил все оборванные дорожки, досконально проверил все соединения и на целостность линий, и на отсутствие замыканий. Положительного результата не получил – карта определялась, но с нулевым объемом. По этой причине она отправилась в ящик ждать «лучших времен».

Прошло 9 лет. В результате очередной уборки-инвентаризации, в ящике нашел эту старую карточку. Вот и настали «лучшие времена», подумал я.

В статье расскажу про микросхему памяти, как определял её адресное пространство, снимал полный дамп подручными средствами (STM32), как определял комбинацию блоков для построения образа, а также про поля Галуа, помехоустойчивое кодирование, вычисление синдромов и локаторов ошибок.

Спойлер - всё получилось.

Часть первая. Аппаратная.

Часть вторая. Теория.

Часть третья. Программная.

Часть четвертая. Кодирование.

Часть пятая. Восстановление данных.

Часть шестая. Итоги.

Часть первая. Аппаратная.

Карта памяти и попытка восстановления дорожек

Как уже писал выше, мне передали сломанную пополам микросхему памяти на 32 Гб.

Перелом идет поперек дорожек, которые соединяют контроллер – каплю и микросхему памяти.

Пробую восстановить дорожки. Сначала зачистил и залудил дорожки.

Зафиксировал плату, чтобы она больше не гнулась в месте перелома и попробовал восстановить дорожки с помощью отдельных жил из МГТФ. На тот момент у меня не было паяльной станции с жалом C115, использовал старую станцию Термит-ПМ36 с заточенным жалом.

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

Значит спустя 9 лет буду пробовать снимать дамп.

Определение распиновки 

Микросхема памяти имеет маркировку Samsung K9PFG08U5M. Технического описания на нее найти не удалось, пришлось решать «загадку»: начал смотреть различные описания на микросхемы памяти Samsung в таком корпусе. По моим наблюдениям, распиновки очень похожи. Есть микросхемы с одним набором шины IO[7:0], есть с двумя. 

На этом моменте стоит определиться с названиями. 

«Микросхемой» буду называть физическую микросхему памяти. 

«Чипом» буду называть минимальную неделимую часть микросхемы, имеющую свой внутренний контроллер, адресацию и работающую независимо.

Если шина одна и внутри один чип, то микросхема имеет следующий набор выводов (VDD и GND присутствуют, естественно, у всех):

IO[7:0], ALE, CLE, R/B, RE, WE, WP, CE

Где:

IO[7:0] – вход/выход, двунаправленная восьмибитная шина, используется для ввода команд, адреса, данных, а также для вывода данных или состояния. 

ALE – вход, сигнал ввода адреса,

CLE – вход, сигнал ввода команды,

R/B – выход, сигнал внутреннего состояния чипа,

RE – вход, сигнал разрешения вывода данных,

WE – вход, сигнал ввода данных,

CE – вход, сигнал выбора чипа.

Бывает, что с одной шиной IO[7:0], у микросхемы два чипа, тогда микросхема имеет следующий набор выводов:

IO[7:0], ALE, CLE, R/B1, R/B2, RE, WE, WP, CE1, CE2

Здесь стоит отметить, что помимо двух сигналов Chip Enable - CE1, CE2, появляются два сигнала Ready/Busy - R/B1, R/B2. Это связано с тем, что запись занимает какое-то время и пока физически, один чип обрабатывает запись, с другим можно работать. Управляющие сигналы, как и шина IO[7:0] мультиплексированы, а сигналы состояния - разные. 

Бывает, что шины IO[7:0] две, тогда к обозначениям выводов дописывается индекс «-1» или «-2».

Например, если микросхема внутри имеет четыре чипа и две шины IO[7:0], тогда микросхема имеет следующий набор выводов:

IO[7:0]-1, ALE1, CLE1, R/B1-1, R/B2-1, RE1, WE1, WP1, CE1-1, CE2-1,

IO[7:0]-2, ALE2, CLE2, R/B1-2, R/B2-2, RE2, WE2, WP2, CE1-2, CE2-2.

Что же у меня. Снимаю микросхему памяти и смотрю на дорожки:

Нашел наиболее похожую распиновку (по количеству используемых выводов) в даташите на микросхему памяти Samsung K9PDG08U5D. Соединяю выводы в соответствии с печатной платой:

Из отличий – в самом нижнем ряду на плате есть вывод GND, а в даташите - это неиспользуемый вывод (NC – Not Connected).

Переходная плата для STM32

Снимать дамп буду с помощью микросхемы STM32H723. Не буду использовать аппаратные контроллеры внешней системной шины, будет старый добрый «ногодрыг» на выводах GPIO.

Для удобства сделал себе распечатку.

PS: В даташите нарисована распиновка на плате, а паяться я буду к выводам микросхемы. Для удобства пайки отразил распиновку. 

Шины данных IO[7:0]-2 и IO[7:0]-1 расположил на одном порту GPIOE для удобства и скорости считывания данных.

Получилась следующая конструкция:

Ни единого намека на защиту от взаимных помех, но будем пробовать.

Фото вместе с программатором (про него писал в моей самой первой статье):

Для проверки работоспособности схемы решил считать идентификатор (ID) из каждого CE. Воспользовался диаграммой из даташита:

Таким образом мне удалось считать ID: 0xEC, 0xDE, 0xD5, 0x72, 0x58, 0x42.

Смотрю, что значат эти данные. Сразу буду писать расшифровки из таблицы. Таблицу взял у одной из микросхем. По моему наблюдению, данные унифицированы. У более старых микросхем, некоторые битовые расшифровки обозначены как «reserved», а в новых, с развитием технологий и увеличения плотности, начинают использоваться.

0xEC – Maker Code

0xDE – Device Code

0xD5 - Internal Chip Number, Cell Type, Number of Simultaneously Programmed Pages

Cache Program – Support

Interleaving operation between multiple chips – Support

Number of Simultaneously Programmed Pages – 2

Cell Type – 4 Level Cell

Internal Chip Number – 2

0x72 - Page Size, Block Size, Redundant Area Size

Page Size – 8KB

Block Size – 1MB

Redundant Area Size - 436B

0x58 - Plane Number, ECC Level, Organization

Plane Number – 4

ECC Level – 24bit

0x42 - Device Technology, EDO, Interface

Пробую читать данные

С расшифровками разобрались, но попробую прийти к ним с обратной стороны, пытаясь читать данные.

Рассмотрю диаграмму чтения данных из памяти:

И рассмотрю стандартную организацию памяти:

Буду считать, что мне ничего неизвестно (в самом начале я НЕ расшифровывал ID, так как не был уверен в корректности расшифровки, используя другой даташит). Собственно, по такому пути я и пошел.

Для чтения байта данных мне нужно передать 7 байт управляющих данных. Это команда 0x00, 5 байт адреса и команда 0x30. 

Как формируются байты адреса. Когда я первый раз открыл даташит на микросхему NAND, мне было непонятно, что это за Page Register. Page Register – своеобразный временный буфер, в который происходит вычитывание всей страницы целиком, а затем уже можно получить произвольный доступ к любому байту считанной страницы.

На следующем фото расшифровка адресации в одном из даташитов. Так получилось, что далее она совпадет с моей адресацией.

Row Address – Адрес непосредственно страницы внутри NAND,

Column Address – Адрес байта на этой странице. 

В зависимости от количества страниц и размера страницы, количество адресных бит в Column Address и Row Address может варьироваться.

Еще по диаграмме чтения можно заметить, что достаточно один раз передать запрос на чтение и далее читать последовательно байты из всей страницы, «щёлкая» сигналом nRE (страница считалась в Page Register и получаем данные из неё).

Примечание: «n» перед именем сигнала будет означать, что активный уровень – логический «0».

Как я буду читать страницы: в Column Address всегда буду передавать 0x0000, а уже количество импульсов nRE будет определять размер считываемой страницы (количество вычитанных данных). С Row Address немного посложней, определимся позже.

Определение размера страницы

Теперь мне недостаточно просто читать байты, а нужно их принимать на ПК.

На микроконтроллере поднимаю USB-CDC (Virtual Com Port). Микроконтроллер получает от ПК адрес страницы, считывает страницу в ОЗУ данных и передает полученные данные на ПК.

На ПК реализовал простую программу на C#. Она будет отправлять адрес страницы, которую необходимо прочитать, а полученные данные сохранит в файл.

Пробую считать 8192 байта из CE1-1, но там оказываются только 0xFF. 

Пробую считать 8192 байта из CE2-1, тут уже непонятный набор данных. видимо, это пользовательские данные. Мне это подходит. Читаю для теста чуть больше, 9000 байт. 

Обращаю внимание, что в байтах с 0 по 8639 идут данные или 0xFF, а с 8640го байта идут 0x00. Пробую прочитать 32768 (0x8000) байт из одной страницы. Обнаруживаю, что начиная с 16384 (0x4000) байта данные повторяются. Отлично, считаю, что я определил количество адресных бит в Column Address – A[13:0]. Причем, 8192 байта – секция данных, а 448 байт – дополнительная секция (по описанию на NAND - DA и SA). Странно, что по расшифровке Redundant Area Size – 436 байт. Будем читать 448, больше не меньше.

Теперь я знаю, что у меня в микросхеме должно быть, как минимум, (32*1024*1024*1024) / 8192 = 4194304 страниц. Но так как у меня 4 разных CE, то в каждом чипе не менее 1048576 страниц.

Определение количества страниц

Буду дальше мучить чип CE2-1. Пробую считать 1048576 (0x100000) страниц. 

Чтобы не убить тестами память на SSD, буду использовать RAM-диск. Выделю для начала 20 Гб и буду собирать дамп туда. 

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

Дружелюбный минималистичный интерфейс программы:

Оставляем на 3,5 часа и у меня чуть больше миллиона файлов. 

Выборочно посмотрев на содержимое файлов, выяснил, что файлы с 0 по 531327 (0x00000-0x81BFF) содержат какие-нибудь не нулевые данные, а остальные содержат только 0x00. Пробую прочитать еще 1048576 файлов.

Итого у меня получилось 2097152 (0x200000) файлов, в которых содержится по 8640 байт данных.

Итого в файлах с номерами 0x00000-0x81BFF и 0x100000-0x181BFF лежат данные, а в файлах с номерами 0x81С00 – 0xFFFFF и 0x181С00 – 0x1FFFFF – нулевые данные.

Получается, что 20-й бит адреса страницы (A33 в Row Address) отвечает за какой-то внутренний мультиплексор.

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

Исходя из этого, в моей микросхеме памяти 4 сигнала CE и еще в каждой – виртуальный CE, т.е. 8 внутренних структур. Мне попадалась маркировка Octal Die, похоже это оно. 

Подведу промежуточный итог

У меня микросхема памяти, которая содержит 4 внутренних чипа. Они в свою очередь, содержат 8 Die (кристалла). Чтобы не путаться, теперь далее буду говорить, что у меня 4 чипа (по номеру CE), а в каждом из них есть 2 кристалла (буду называть DIE0 и DIE1).

В каждом DIE 0x81C00 (531456 страниц).

Размер блока 

Во всех микросхемах, которые похожи по объему и распиновке на мою, в блоке содержится 128 страниц. Попробую подставить это количество и посмотрю на количество блоков.

531456 / 128 = 4152 блока. 

С учетом того, что у меня теперь 8 кристаллов (DIE), то в каждом кристалле должно быть не менее 32/8 = 4Гб данных, а значит не менее (4*1024*1024*1024) / 8192 = 524288 страниц или 4096 блоков, а у меня их больше. 

У меня получается следующая блочная структура в пределах одного кристалла:

Снимаю полный дамп

Как писал в самом начале, я подключил обе шины IO[7:0]-1 и IO[7:0]-2 на один 16-битный порт GPIOE. Сигналы RE1 и RE2 тоже сидят на одном GPIO. Подумал, что таким образом смогу быстрее считывать данные, но оказалось, что RE1 и RE2 (несмотря на то, что переключаю их в STM32 одновременно через BSSR) влияют друг на друга (или шина IO влияет и происходили лишние запуски чтения), пришлось раздельно дергать RE1 и RE2 и читать данные по отдельности. 

Расширил мою программу до следующего вида:

Теперь 8 кнопок запускают циклический опрос страниц в рамках одного кристалла (DIE) и дамп сохраняется в единый файл. Все-таки с одним файлом работать быстрее, чем с миллионами маленьких. А кнопка START запускает поочередное считывание всех 8 дампов.

Пришлось увеличить RAM диск до 40 Гб.

Запускаю считывание. 12 часов и все 8 дампов, суммарно на ~34.2Гб готовы.

Оцениваю полный дамп

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

Теперь все страницы одного DIE собраны в один файл, а их размер 0x21C0. Это значит, что PAGE0 (Начало Block0) начинается с адреса 0x0, PAGE1 начинается с адреса 0x21C0 и т.д. PAGE128 (Начало Block1) начинается с адреса 0x10E000 (0x21C0 * 128).

У меня есть основной блок (Data Area) размером 0x2000 и дополнительные данные (Spare Area). Вот с последними и буду разбираться. Мне пока ничего не известно ни про ECC, ни про дополнительные данные. Будем, как говорится, посмотреть.

Я обратил внимание, что на всех 128 страницах одного блока - байты 0x2151 и 0x2152 одинаковые, а у следующего блока они другие, но тоже одинаковые в рамках своего блока. 

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

Написал программу – конвертор, которая проанализирует все 8 дампов и выведет мне все эти данные. Получилось 30552 не пустых и 2665 пустых блоков - которые в байтах 0x2151 и 0x2152 содержат 0x00 или 0xFF. Но блоки с «пустыми» номерами заполнены полностью 0x00 или 0xFF. Исключу эти блоки из оценки. 

Рассмотрю файлы CE1-1-DIE1.bin и CE1-2-DIE1.bin, в них по смещению 0x2150 присутствует одинаковый набор байт D4 F6 67 FF FE A4 1F DB в байтах 0x2151 и 0x2152 - 0xF6 и 0x67). Таких наборов в каждом из файлов – 256 штук (по одному набору в каждой из страниц и по 128 в каждом блоке)

Внимательно рассмотрев эти листинги по 2 байта, заметил, что они похожи на номера блоков, но данные инвертированы. 

Провел дополнительный анализ уже инвертированных данных, собрал значения в 16 бит, где байт 0x2151 – старшая часть, а байт 0x2152 – младшая часть. 

Посчитал, сколько блоков имеют одинаковые номера и оказалось, что таких блоков по 4 штуки, причем 2 блока в одном кристалле одного чипа и идут подряд, а 2 в другом чипе. 

Например, блоки с номером 00 01 расположены в дампах CE2_1_DIE1 и CE2_2_DIE1.

Думаю, что это связано с оптимизацией записи данных. В даташитах даже есть специальное название «Plane»

Собрал матрицу «существующих» и «отсутствующих» блоков.

Вывел результат, где «[]» - блоков с таким номером обнаружено 4шт, а «__» - блоки с таким номером отсутствуют.

Думаю, что это успех, по 4 блока с каждым номером. 

Введу дополнительное обозначение. Назову 4 блока с одним номером - главой. Возможно, есть другое название, но я не встретил. 

Итак, у меня есть множество глав, но как 4 блока расположены внутри одной главы – неизвестно. 

Порядок блоков

Рассмотрю 4 блока первой главы.

В исходном виде в дампе – непонятные символы, но если проинвертировать, то появляются читаемые данные.

И тут я вижу читаемые символы, значит я на верном пути.

С учетом того, что и нумерация глав тоже была в инверсии, проинвертирую абсолютно все дампы. Очень похоже, что запись в этом контроллере идет в инверсии для снижения нагрузки на ячейки (NAND память очищает сразу целый блок. При очистке все ячейки имеют значение 0xFF, а запись – программирование нулевых бит, соответственно, пустые блоки с 0x00 при записи будут 0xFF). Есть множество других хитрых алгоритмов, но мне повезло.

Пришлось увеличить RAM диск до 80 Гб, чтобы проинвертировать весь дамп, не удаляя исходный.

В инвертированном дампе CE1-1 DIE0, по адресу 0x21c000 (начало PAGE2) читаемые данные:

Похоже, что в капле – контроллер Silicon Motion SM2683, но мне это никак не помогает. У этого контроллера, по найденной мной информации, бывают разные прошивки с конфигурациями, однако наблюдение интересное.

Двигаюсь дальше.

Как заметил выше, блоки с одинаковым номером лежат в файлах 

либо в CE1_1_DIE0 и CE1_2_DIE0; 

либо в CE1_1_DIE1 и CE1_2_DIE1; 

либо в CE2_1_DIE0 и CE2_2_DIE0; 

либо в CE2_1_DIE1 и CE2_2_DIE1.

И в каждой паре файлов данные лежат на одинаковом смещении. 

Буду проходить по парам этих файлов и собирать каждую главу в один файл. Сначала будут идти 256 страниц из первого файла, а затем 256 страниц из второго. Получатся файлы по 44423680 байт.

Теперь мне нужно как-то собрать эти 4 блока в нужном порядке. Для удобства следования, назову их BLOCK0, BLOCK1, BLOCK2 и BLOCK3, каждый содержит 128 страниц (PAGE0 – PAGE127).

Рассмотрю Главу 1:

Смотрю, что на смещении 0x21C0 (PAGE1) начинают идти следующие данные:

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

На каждой странице идет 8 наборов с комбинацией 1024-42, но с этим разберусь позже, слежу за закономерностью.

BLOCK0, PAGE1 заканчивается набором 00 12 00 00, а PAGE2 начинается набором 01 2a 00 00. 

BLOCK1 начинается со следующих символов: 01 12 00 00 02 12 00 00

BLOCK2 начинается со следующих символов: 01 1a 00 00 02 1a 00 00

BLOCK3 начинается со следующих символов: 01 22 00 00 02 22 00 00

Рассмотрю все в рамках PAGE1 и представлю числа как uint32 с little endian.

BLOCK0: начало 0x00000A01, конец 0x00001200

BLOCK1: начало 0x00001201, конец 0x00001A00

BLOCK2: начало 0x00001A01, конец 0x00002200

BLOCK3: начало 0x00002201, конец 0x00002A00,  

Далее 

BLOCK0 PAGE2: начало 0x00002A01, конец 0x00003200. Думаю, что этого достаточно, чтобы попытаться применить данный порядок.

То есть данные собираю в главы последовательно:

ГЛАВА[X][0] = BLOCK0 PAGE[0], BLOCK1 PAGE[0], BLOCK2 PAGE[0], BLOCK3 PAGE[0]

...

ГЛАВА[X][127] = BLOCK0 PAGE[127], BLOCK1 PAGE[127], BLOCK2 PAGE[127], BLOCK3 PAGE[127].

Собираю все 8 дампов в один большой дамп в нужной последовательности. Если глава отсутствует, то заполняю её нулями, на всякий случай.

Дамп с ошибками

Из шага выше заметил, что на каждой странице идет 8 наборов с комбинацией 1024-42, попробую сделать «грязный» дамп, т.е. дамп, отрезав «лишние» 42 байта (думаю, что это – коррекция ошибок, но я пока не знаю, как она работает).

Пишу программу, которая будет проходить по всему отсортированному дампу, считывать страницу (8640 байт), брать из нее 8 секторов (как позже выяснил, их называют Sector) по 1024 байта, пропуская 42 байта и отбрасывая все, что осталось в конце (112 байт). Все полученные данные соберу в один большой дамп. Это уже будет «грязный» образ карты памяти.

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

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

Вот одна из самых «читаемых»

Вроде файлы есть, все файлы битые, но все-равно считаю, что это успех.

Повторное чтение страниц

Решил провести эксперимент – прочитал одну и ту же страницу 8 раз, а затем побитово сравнить полученные файлы. Все 8 файлов оказались разными. 

Действительно, даже в новой NAND памяти допустимо некоторое количество ошибок на страницу. 

Поиск решения по коррекции ошибок

Нужно разобраться с коррекцией ошибок. Без нее всё проделанное выше – бессмысленно.

Итак, возьмем наше наблюдение по упаковке данных в структуры 1024-42. Ищу в интернете информацию и нахожу такую табличку

Такая табличка мне понравилась, тут многое сходится. У меня Sector Size 1024 байта, ECC 42 байта, а из считанного и расшифрованного ID микросхемы, ECC Level – 24bit.

Что же значат заветные буквы BCH, а это ни что иное, как кодирование Боуза-Чоудхури-Хоквигема (предположительно).

Часть вторая. Теория.

Здесь понадобится немного математики

Начинаю искать информацию про кодирование. Нахожу очень хорошие лекции (Криптография без секретов) по 2 академических часа. Интересующая меня тема значится под номером 13. Начинаю слушать, вспоминая теорию полей и колец из курса алгебры, расчехляю старые лекции из ВУЗа, но понимаю, что мне не хватает понятийного аппарата, к которому пришли на 13-й лекции. Начинаю изучать лекции с начала. Очень познавательный материал, прошло более 14 часов, и я понимаю каждое слово в лекции номер 13. Затем изучаю две лекции с канала Codes and Signals и полирую полученные знания статей с Хабра «Кодирование Рида Соломона для чайников».

Сейчас буду пытаться развернуть полученную информацию.

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

Группа

Разберем некоторое множество (назовем его G) элементов с бинарной операцией (операция над двумя элементами). Обозначу нашу абстрактную операцию как т в кружочке (от слова transformation – преобразование). 

Группа – это множество элементов G с бинарной операцией т в кружочке, обладающая свойствами:

1. Замкнутость. Для любых элементов a и b из множества G, результат операции c

тоже принадлежит множеству G.

2. Ассоциативность. Для любых элементов a, b и c из множества G, выполняется равенство

3. Наличие нейтрального элемента. Существует элемент e из множества G такой, что для любых элементов a из множества G, выполняются равенства 

4. Наличие обратных элементов. Для любого элемента a из множества G существует обратный элемент такой, что 

Если результат выполнения операции не зависит от порядка (свойство коммутативности) 

то такую группу называют коммутативной группой или Абелевой группой (в честь Нильса Абеля).

Рассмотрю пример: 

Возьму множество целых чисел с операцией сложения «+»:

1. Замкнутость. Какие бы 2 числа я не складывал, всегда получу целое число (1+2=3), (2+(-4)=-2) и т.д.

2. Ассоциативность. От перемены мест слагаемых, сумма не меняется: (1+2)+3=1+(2+3)=6. 

3. Нейтральный элемент. Нейтральный элемент – 0: 0+5=5+0=5.

4. Обратный элемент. Для любого элемента, допустим 7, всегда найдется элемент -7: 7+(-7)=0.

Значит множество целых чисел с бинарной операцией «+» является группой, к тому же это Абелева группа.

А вот множество целых чисел с операцией умножения «*» уже не будет являться группой, т.к. обратные элементы – это дроби (рациональные числа).

Множество рациональных чисел (если исключить из них 0) с операцией умножения «*» уже будет являться группой, причем Абелевой группой.

Возьму менее привычное множество – группа по модулю 4 (mod 4) и операцию сложение «+».

Множество элементов G содержит элементы с 0 по 3: G = {0,1,2,3}. Если в результате операции сложения получается число больше или равное модулю «4», то нужно взять остаток от деления на 4. Допустим, 2+3 = 5, 5 mod 4 = 1 (остаток от деления). Значит в нашем конечном множестве, результат операции 2+3 = 1. Построю полную таблицу:

По таблице становится проще находить обратный элемент. Например, для 3 обратный элемент 1, т.е. 3+1 = 0. Это тоже группа и даже Абелева группа.

Подгруппа

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

А для того, чтобы подмножество H группы G являлось подгруппой, необходимо и достаточно, чтобы:

1. для любых a и b из H результат бинарной операции принадлежал H

2. для любого элемента множества H, его обратный элемент тоже принадлежал H

Циклическая группа

Группа, состоящая из степеней одного элемента a, называется циклической группой.

Например, G – мультипликативно записанная группа (операция в G - умножение), для произвольного элемента a рассмотрю «произведения» вида 

называются степенями элемента a и обозначаются 

Нейтральный и обратный элементы:

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

Некоторый свойства, которые пригодятся:

В любой конечной группе порядок каждого элемента конечен. 

В конечной группе порядок любого элемента - делитель порядка группы.

Любая группа простого порядка циклическая.

Кольца

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

1. Множество A с аддитивной бинарной операцией – является Абелевой группой

2. Бинарная мультипликативная операция ассоциативна

3. Операции аддитивная и мультипликативная связаны дистрибутивными законами, т.е.

Если мультипликативная операция в кольце обладает нейтральным элементом, то говорят, что A – кольцо с единицей.

Если мультипликативная операция обладает коммутативным свойством, то такое кольцо называют коммутативным кольцом.

Характеристика кольца

Если A – кольцо с единицей, то целое положительное число m называют характеристикой кольца A, если

Векторы

Множество пар целых чисел (двумерные векторы) тоже образует кольцо. Пример аддитивной операции:

Аналогично и для векторов размерности n.

Обратные элементы

Обратные элементы в кольце целых чисел есть только у 1 и -1, а в множестве рациональных чисел обратимы уже все ненулевые элементы.

Поле

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

Обратным элементом по мультипликативной операции называется такой элемент, который образует нейтральный элемент с исходным

Операция «деления» на элемент в поле преобразуется в следующее выражение:

Поле не имеет «делителей» для нулевого элемента, т.е. обратного элемента для нуля нет.

Полиномы

Полиномом (или многочленом) от неизвестной x над кольцом A называется выражение вида

Элементы a называются коэффициентами полинома, все они или их часть могут быть нулевыми.

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

Наибольшее k такое, что

называется степенью полинома и обозначается как deg f

Множество всех полиномов от x с коэффициентами из кольца A обозначается символом A[x].

Операции сложения и умножения определяют на множестве A[x] структуру кольца.

Полином g(x) из кольца K[x] называют приводимым (над полем K), если существуют такие полиномы, что:

в противном случае полином g(x) называется неприводимым.

Расширения полей

Если g(x) – неприводимый полином над полем K, то кольцо классов вычетов кольца K[x] по модулю g(x) является кольцом без делителей нуля.

Кольцо классов вычетов L = K[x] / (g(x)) по модулю неприводимого полинома есть поле.

Любое расширение L поля K можно рассматривать как векторное пространство над K. Базис этого векторного пространства состоит из полиномов (классов, которым принадлежат эти полиномы)

где, n=deg g(x). Размерность n этого пространства называют степенью расширения L над K.

Любое конечное поле характеристики p состоит из p в степени n элементов для некоторого n.

Конечные поля, содержащие p в степени n элементов, называются полями Галуа и обозначаются как

Пример 1: 

полином неприводим над полем GF(2), так как ни 0, на 1 не являются его корнями

Существует свойство: r является корнем, если g(r) = 0. Вычислим: g(0) и g(1) в соответствии с аддитивной и мультипликативной операциями

g(0) = 1, g(1) = 1

В полях Галуа характеристика кольца = 2, а значит обратный элемент равен самому элементу и -a = a, разность можно заменять суммой, а сумма двух одинаковых элементов – нейтральный элемент по аддитивной операции и равна нулю. Эти свойства помогут построить GF(4) по модулю вышеуказанного неприводимого полинома.

Пусть j – корень вышеуказанного неприводимого полинома, тогда из равенства

построю таблицы для аддитивной и мультипликативной операций

Пояснение:

Пример 2:

Построю GF(8) по модулю неприводимого полинома 

Общий вид элемента поля GF(8) можно записать в виде

Или просто в виде двоичного вектора 

Построю таблицу для аддитивной операции

Построю только одну половину, так как в силу свойства коммутативности эта таблица симметрична относительно главной диагонали. Сложение в расширении поля ни что иное, как операция xor (исключающее или), так как характеристика кольца = 2. В связи с этим наблюдением, больше не будем строить таблицу аддитивной операции.

Построю таблицу для мультипликативной операции

Пояснение:

Мультипликативная группа конечного поля 

В поле Галуа все ненулевые элементы являются степенями одного элемента. 

Например, используя таблицу из примера 1, в GF(4):

Генераторный полином

Рассмотрю GF(8) с указанным в примере 2 неприводимым полиномом.

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

Нулевая степень — это всегда единичка. Чтобы получить значение первой степени – сдвигаем влево значение предыдущей степени. Повторяем действие для второй степени. Чтобы получить значение третьей степени, нужно еще повторить действие, но единичка, которая двигалась по значению выходит за границу размерности. В случае, когда такое происходит, необходимо произвести некоторые действия.

Берем порождающий полином и выражаем из него 

Каждый раз, когда при сдвиге значения единичка «выходит» за предел размерности, буду применять аддитивную операцию (в нашем случае xor) к оставшемуся значеню и правой части вышеуказанной формулы (в бинарном виде порождающий полином записывается как 1101):

Мультипликативная группа конечного поля GF(q) является циклической группой порядка q-1.

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

Из таблицы можно заметить, что при умножении двух элементов, их степени складываются. Если степень равна или превышает q-n (в нашем случае q-n=8-1 = 7), то берется остаток от деления степени по модулю.

Часть третья. Программная.

Программная реализация операций над двумя элементами

Для реализации программного вычисления результатов аддитивной и мультипликативной операций над элементами поля Галуа, необходимо:

1. Построить таблицу всех степеней поля (pow_tab), таких степеней будет q-1 (массив размером q-1).

Строю её с помощью генераторного полинома по рассмотренному выше алгоритму (сдвиг и xor)

Если обратиться по индексу массива, то получу значение элемента в степени индекса массива.

Например, для GF(8):

2. Построить таблицу логарифмов поля (log_tab). Для этого нужно построить q-1 отображение (еще один массив размером q-1, но так как значение всех степеней – это ненулевые элементы, то массив будет размером q, но нулевой элемент использоваться не будет, для простоты записи операций). 

Пробегусь по всему массиву степеней поля и «поменяю местами» степень и индекс.

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

3. Реализовать аддитивную операцию.

Ну здесь все просто – я беру два элемента, произвожу операцию исключающего «или» (xor) и возвращаю результат.

4. Реализовать мультипликативную операцию.

Тут необходимо реализовать операцию с ограничением.

Если хотя-бы один из двух элементов – нулевой, то и результатом операции будет нулевой элемент.

Если оба элемента не нулевые, то необходимо найти, по таблице log_tab, степень каждого элемента, полученные степени сложить, взять остаток от деления на q-1 (исключить выход за границу) и используя таблицу pow_tab вернуть значение элемента:

5. Обратный элемент 

Необходимо найти такой элемент, чтобы результатом мультипликативной операции с исходным была 1:

Программная реализация работы с полиномами

Для сокращения записи полиномов, введу сокращение записи:

Рассмотрю полином

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

С таким представлением полиномов можно программно реализовать математические операции в поле:

1. Аддитивная операция над двумя полиномами.

Реализация – аддитивная операция над каждой парой коэффициентов полинома. Полиномы могут быть различной степени, результатом операции является полином наибольшей степени:

2. Операция возведения полинома в степень.

Ни что иное, как мультипликативная операция над полиномом и полиномом x в степени k:

Просто увеличиваем размер массива на k элементов, добавляя k нулевых элементов (коэффициентов) в начало массива.

3. Мультипликативная операция над полиномом и элементом поля.

Реализация – необходимо применить мультипликативную операцию над элементом поля и каждым коэффициентом полинома.

4. Мультипликативная операция над полиномом в общем виде и полиномом с единственным коэффициентом.

Ничто иное, как мультипликативная операция над полиномом и элементом поля и возведение полинома в степень k.

5. Мультипликативная операция над двумя полиномами.

Тут уже нужно сделать больше действий, как в умножении многозначных чисел. 

Виртуально разобьем один из полиномов степени k на k+1 полиномов с единственным коэффициентом, а затем произведем k+1 мультипликативных операций над вторым полиномом степени n и полученными полиномами с единственным коэффициентом. В результате получу k+1 полином, с которыми необходимо последовательно провести аддитивные операции над двумя полиномами.

Результатом такого вычисления станет полином степени k+n или массив размера k+n+1. Все как с умножением столбиком, но в поле Галуа.

6. Поиск делителя 

Мне может понадобится такая операция, как вычисление частного

Алгоритм вычисления частного очень похож на вычисление частного при делении многозначных чисел.

Например, я хочу разделить полином f(x) степени n на полином g(x) степени k, результатом такого деления станет частное и остаток от деления. 

Частое – полином s(x) степени n-k+1.

Чаще всего интересует именно остаток от деления – полином r(x) степени k-1. 

Чтобы произвести вычисления, необходимо n-k+1 раз провести поиск коэффициента частного:

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

После произведенных действий, степень полинома f(x) уменьшится и станет n-1.

Осталось повторить действия n-k раз, в результате чего полином f(x) превратится в полином степени не большей, чем k. Полученный полином и будет полиномом остатка.

Пример:

Часть четвертая. Кодирование.

Помехоустойчивое кодирование

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

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

Самым простым примером помехоустойчивого кодирования является троирование.

Передам одни и те же данные три раза. Если какие-то данные в одной из трех передач исказятся, мы и обнаружим, что ошибка была, и скорректируем данные (при условии, что в двух других передачах этой ошибки не было).

Пример:

Я хочу передать данные (информационный вектор, размерность k = 7) 1000110,

Передаем его три раза (кодовый вектор, размерность n = 21) 100011010001101000110,

Приняли данные с ошибкой (принятый вектор, размерность n = 21) 100011010101101000110,

Простым анализом «на глаз» определяем, где у нас ошибка.

1000110

1010110

1000110

Нахожу позицию ошибки в принятом векторе (вектор ошибки, размерность n = 21) 000000000100000000000.

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

Реализованный метод кодирования есть ни что иное, как КОД (21,7). Данный код корректирует до 7 не случайных ошибок. 

Примечание: если бы мы передавали данные два раза, а не три, то невозможно верно скорректировать ошибку (неизвестно, какие из двух данных - ошибочны), но можно ее обнаружить.

Бит паритета (четности)

Например, в слове приемопередачи по RS232 или МКИО есть бит паритета. (у RS232 настраиваемый)

Это значит, что помимо основных данных еще передается бит четности – указывает на количество «1» в переданном бинарном слове данных. В одних реализациях этот бит «1» если в слове данных четное количество «1», в других, если нечетное. Такой механизм позволяет обнаруживать единичную ошибку, но не исправить.

Например, для RS232 – это КОД (9,8), для МКИО – это КОД (17,16). Стартовые, стоповые, биты синхронизации и т.п. не учитываю.

Код Хэмминга

Код Хэмминга – более оптимальный алгоритм, позволяющий корректировать ошибки.

Рассмотрю КОД(7,4)

Кодовый вектор получается из умножения матриц:

Но все намного проще: если i-й бит присутствует, то i-я строка участвует в сложении (операция xor)

Рассмотрю пример для информационного вектора (1001):

Кодовый вектор (1001110). Допустим, во время передачи произошло изменение одного бита и получили принятый вектор (1011110), нужно вычислить синдром. Здесь, как с болезнью – в соответствии с определенным синдромом - соответствующее лечение. Если количество ошибок не вышло за пределы корректирующей способности, то синдром однозначно определит ошибку (болезнь).

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

Произведу эти действия с принятым вектором:

В данном случае, значение синдрома не указывает в явном виде на номер позиции ошибки, но имея таблицу соответствия позиции ошибки синдрому, можно найти вектор ошибки и исправить принятое сообщение:

Наш синдром 110 указывает на ошибку в 3-м информационном бите (если начинать считать с 1), т.е. получаем вектор ошибки (0010000). Чтобы восстановить исходный информационный вектор, необходимо произвести операцию xor: (1011110)^(0010000) = 1001110. 

Примечание: Если синдром 000, то ошибок в принятом векторе нет.

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

Часть пятая. Восстановление данных.

Рассуждения

Я просмотрел и прочитал достаточно много теории перед данным этапом, но не думал, что разобраться будет так не просто. 

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

А также из различных описаний ранее: Sector Size 1024 байта, ECC 42 байта, ECC Level 24bit.

Для таких размерностей применяется расширение поля Галуа 

с порождающим неприводимым полиномом 17475 (dec) = 0x4443 (hex).

Где правая часть представляет собой запись в бинарном виде: 00 0100 0100 0011 

Снова написал табличную реализацию pow_tab и log_tab, где уже было 16383 и 16384 элемента соответственно (в log_tab снова нулевой элемент не используется, но для простоты обращения присутствует) 

Пример генерации элементов поля (таблицы pow_tab)

Разобравшись (как мне кажется) с классическими алгоритмами кодирования и декодирования БЧХ, а также с кодами Рида Соломона, стал пробовать применять полученные знания.

Если с корректирующими данными все было «нормально» и 42 байта по 8 бит (336 бит) очень хорошо раскладывались в 24 символа по 14 бит, то с 1024 байтами данных так складно не получилось. 

Пробовал в соответствии с теорией, сделать порождающий полином 48 степени для кодов Рида Соломона, используя последовательно 48 степеней, начиная и с 0 и с 1й.

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

Я пробовал дополнять нулями данные для выравнивания, крутил последовательность данных и крутил корректирующие коды, пробовал разные «сборки» в битовую последовательность – и big endian и little endian. Результата мои попытки не принесли, ничего не выходит, стал искать решение. 

В литературе ничего похожего не нашел и почти отчаялся. Ну не может же так быть, что нигде не описан алгоритм, который используется «каждый день» в наших флешках. Начал искать реализации и нашел на GitHub несколько репозиториев, которые используют один и тот-же комплект файлов bchlib (.с и .h) в папках NAND (в том числе, в составе некоторых прошивок). Попробовал прогнать мои тестовые секторы через этот алгоритм, и оно заработало! 

Вроде, работает – не трогай, но нужно разобраться, что это за хитрый алгоритм, достаточно оптимизированный и использует более 11кб ОЗУ для генераторных таблиц.

Начинаю разбираться.

Порождающий полином BCH

Если в классических кодах Рида Соломона необходимо использовать степени «подряд», то здесь все несколько иначе:

Используются 24 группы по 14 корней. Степени этих корней построены следующим образом: первая степень – нечетное число, а последующие 13 степеней – последовательное возведение в квадрат первой:

Количество групп соответствует корректирующей способности кодирования – 24 бита.

Где в каждой группе первый элемент – нечетное число, а каждое последующее – его произведение на характеристику поля = 2 (с коррекцией на переполнение, если вышли за границу 16383, но нужно взять остаток от деления:  12288*2 = 24576 (mod 16383) = 8193).

Общий вид:

Если попытаться сделать 15й элемент (допустим 8193*2 = 16386 (mod 16383) = 3), то он совпадет с первым корнем. Построение циклотомического класса прекращается, как только число начинает повторяться. В общем случае, количество элементов циклотомического класса не всегда равно степени расширения поля.

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

Множество целых чисел, отображающих степени примитивного элемента a поля 

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

Каждый циклотомический класс однозначно соответствует одному из неприводимых сомножителей 

Используя теорему Этьена Безу, составлю полином, корнями которого будут корни со степенями одного из циклотомических классов. Это будет полином 14-й степени, так как корней ровно 14.

В используемом расширении поля Галуа обратный элемент по сложению является самим элементом, значит меняем разность на сумму:

Подставлю значения

Начну раскрывать скобки (не забываю, что все действия происходят в поле – сложение xor, умножение – сложение степеней):

Интересное наблюдение – полученный полином имеет единичные коэффициенты, как и полиномы, полученные для каждого циклотомического класса.  

В результате произведения полиномов, полученных из вышеуказанных 24х циклотомических классов, получится порождающий полином степени 336:

В классическом алгоритме Рида Соломона, чтобы получить систематический кодовый вектор, необходимо к информационному вектору добавить корректирующий вектор.

Чтобы получить корректирующий вектор – необходимо:

Из информационного вектора получить информационный полином (элементы информационного вектора становятся коэффициентами полинома), 

Возвести информационный полином в степень k (длина корректирующего вектора)

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

Коэффициенты полинома остатка и будут корректирующим вектором.

В моем случае, это бы происходило в поле GF(16384), но в NAND используется другой алгоритм - операции производятся в поле GF(2)

Полученный генераторный полином 336 степени сворачивается в 337 битное число, где каждый коэффициент полинома – бинарная позиция в новом генераторном полиноме.

Мой генераторный полином превращается в 337 битный генераторный вектор:

0xC74A7012 46C84E95 A292B968 F6ECE84C 7F398747 46936169 1449D1D0 242DE855 B705A4C9 4D1AB5EA 18778000

Для удобства проведения последующих операций, я его выровнял до 32 бит и сдвинул до старшей степени (влево), младшие 15 нулевых бит не используются, но и не будут влиять на результат.

Корректирующий вектор

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

Необходимо взять информационный вектор (1024 байта или 8192 бит), возвести в 336 степень в поле GF(2) – дополнить его 336 битовыми нулями (информационный вектор увеличится до 8528 бит) и разделить на полученный генераторный вектор размером 337 бит, из результата деления необходимо взять остаток в виде 336 бит.

Как это сделать:

Деление в поле GF(2) – простейший последовательный xor. Я беру данные из NAND Главы[1] (где было прочитано заветное слово FAT32), нулевой сектор (big endian):

0xEB009020 20202020 20202000 02402C00 02000000 00F80000 3F00FF00 00200000 0058C203 EA1F0000 00000000 02000000 01000600 ...

eb 00 90 20 20 20 20 20 20 20 20 00 02 40 2c 00
02 00 00 00 00 f8 00 00 3f 00 ff 00 00 20 00 00
00 58 c2 03 ea 1f 00 00 00 00 00 00 02 00 00 00
01 00 06 00 00 00 00 00 00 00 00 00 00 00 00 00
80 00 29 00 00 00 00 4e 4f 20 4e 41 4d 45 20 20
20 20 46 41 54 33 32 20 20 20 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 55 aa
52 52 61 41 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 72 72 41 61 b5 32 00 00 ad d5 0e 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 55 aa

a1 18 11 fd 97 1c 2b 36 b4 c8 55 7d d2 04 9d 64
11 3a ee c3 8b e1 a2 3e ed 1d 25 e5 44 1e 3e 7f
df e8 a9 08 76 42 2a 41 dd db

Если самый старший бит = 1 (0xE = 1110, старший бит = 1), то выполняю xor генераторным вектором и сдвигаю полученный результат влево на 1 бит:

0x5895C064 CDD0DD6B 056532D1 E9598898 FA730E8E 8CD6C2D2 56925DA0 481BD0AB 6EBACD95 4E0B6BD4 30EF0000 04000000 02000C00 ...

Самый старший бит = 0 (0x5 = 0101, старший бит = 0), то НЕ выполняю xor, а просто сдвигаю полученный результат влево на 1 бит.

Повторяю шаги еще 8190 раз и получаю остаток - корректирующий вектор

0xA11811FD 971C2B36 B4C8557D D2049D64 113AEEC3 8BE1A23E ED1D25E5 441E3E7F DFE8A908 76422A41 DDDB

Для удобства выравниваю:

0xA118 11FD971C 2B36B4C8 557DD204 9D64113A EEC38BE1 A23EED1D 25E5441E 3E7FDFE8 A9087642 2A41DDDB 

Он совпал с 42 байтами коррекции, записанными в NAND. Считаю, что это еще одна маленькая победа, но это только начало. 

Вообще, в программной реализации, которую я нашел, не производится такое «затратное» деление со сдвигом, все оптимизировано через табличный метод (генерируются таблицы для быстрого вычисления блоками по 8 бит), но для понимания процесса, буду делать всё напрямую.

Вычисление синдромов

Если с валидными данными все получилось, то необходимо выяснить, как искать ошибки.

В классическом алгоритме Рида Соломона для поиска синдромов, необходимо в информационный полином подставить корни, из которых образован генераторный полином. Таким образом, каждый корень даст свой коэффициент синдрома.

Здесь все оказалось немного иначе:

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

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

Добавлю ошибки в 3 бита: 0-й, 15-й и 8175-й (порядок big endian). Начало данных теперь выглядит следующим образом: 

0x6B019020 20202020 20202000 02402C00 02000000 00F80000 3F00FF00 00200000 0058C203 EA1F0000 00000000 02000000 01000600 ...

Вычислю новый корректирующий вектор:

0xA810 16A07C66 6B7F1DA2 D2D6DCA1 DD5DB9CC B941370F DCF03007 3834A05D 0F7DE472 D6E9623A B85A19E8  

Корректирующий вектор в NAND (считанный):

0xA118 11FD971C 2B36B4C8 557DD204 9D64113A EEC38BE1 A23EED1D 25E5441E 3E7FDFE8 A9087642 2A41DDDB  

XOR двух корректирующих векторов:

0x0908 075DEB7A 4049A96A 87AB0EA5 4039A8F6 5782BCEE 7ECEDD1A 1DD1E443 31023B9A 7FE11478 921BC433  

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

Пока разбирался в алгоритме, выяснил, что вычисляются 48 синдромов (на корректирующую способность в 24 бита), но происходит вычисление только для нечетных синдромов, четные синдромы вычисляются из квадратов нечетных синдромов.

Значит необходимо вычислить 24 нечетных синдрома: 1,3,7…47 (как и номера циклотомических классов). Вычисляются синдромы следующим образом:

Изначально наш массив синдромов нулевой. 

Пробегаемся по нашему новому полученному вектору с младшего (0) до старшего бита (335) - 366 раз делам следующее: 

если бит в текущей позиции (bit_pos) не нулевой, то к каждому нечетному синдрому (таких 24) прибавляем (операция xor) вычисленное значение по следующей формуле:

Где i – нечетный синдром, а произведение i на позицию бита ограничено сверху n-1 = 16383. 

В результате всех вычислений получаю следующие синдромы:

Вычисление локатора ошибок

Цель данного шага – найти полином локатора ошибок. Степени корней полинома локатора ошибок указывают на точные позиции, в которых перевернулись биты.

На фото ниже я пытаюсь разобраться в алгоритме:

Я в этот момент:

Что из себя представляет этот полином и какие у него свойства?

Представим, что мы знаем, что у нас 2 ошибки в данных, тогда наш полином локатора ошибок C(x) имеет степень 2. Он должен обладать следующими свойствами:

Это ни что иное, как поиск кротчайшего регистра сдвига с линейной обратной связью (РСЛОС или LFSR). Статья и так вышла большой, думаю, если вы дочитали до этого места, то сами найдете информацию про РСЛОС, а я попробую не углубляться в детали.

В итерациях шагов пропускаются четные синдромы. Скорее всего, это связано с тем, что они вычисляются из квадратов нечетных синдромов и не несут «новой» информации.

Для поиска полинома локатора ошибок используется модифицированный алгоритм Берлекэмпа – Мэсси. Здесь многое иначе: и порядок произведения, и множитель x в степени m в формуле вычисления C(x) - в другом слагаемом, но алгоритм в таком виде - работает.

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

Для реализации данного алгоритма понадобятся вспомогательные элементы:

d – текущее расхождение, C(x) – текущий полином - локатор (инициализируется как C(x) = 1)

Элементы, которые были изменены на прошлом расхождении:

b – значение прошлого не нулевого расхождения (инициализируется как 1), B(x) – копия полинома – локатора на прошлом расхождении (инициализируется как B(x) = 1), а также m – количество итераций, прошедших с прошлого расхождения.

Если расхождение d не нулевое, то вычисляем

Покажу работу алгоритма на примере

На первых трех шагах вычислен полином локатора ошибок, а на шагах 4-24 прошла проверка, что он подходит.

Вычисление позиций ошибок

Чтобы вычислить позиции ошибок, необходимо найти корни полинома локатора ошибок.

Есть оптимальные алгоритмы, но я пойду простым путем – переберу все элементы поля.

Если q – корень, то подставив C(q) получу 0.

Таким образом я нашел 3 корня: 

Пример:

Степени корней полинома локатора ошибок найдены – 352, 8512 и 8527, но ошибки вносились в биты 0-й, 15-й и 8175-й (порядок big endian).

Получается, что наши позиции бит считаются с обратной стороны. Всего в кодовом слове 8192 + 336 = 8528 бит и считаются с 0 по 8527.

Чтобы получить исходные позиции, необходимо вычесть из 8527 наши полученные степени – позиции.

8527 – 352 = 8175

8527 – 8512 = 15

8527 – 8527 = 0

Можно либо отдельно инвертировать каждый из трех бит, либо составить вектор ошибки и применить xor к принятому вектору.

Часть шестая. Итоги.

Коррекция данных в NAND

Сначала я применил данный алгоритм для коррекции считанного дампа. 

Момент истины, собираю «чистый» дамп, провожу анализ файлов и мне удалось восстановить даже файловую систему.

Одна из восстановленных фотографий:

А эта фотография похожа на ту, что была из «самых читаемых» в грязном дампе:

Получил довольно приличный результат, но все-равно имеется не мало ошибок и множество больших фотографий (особенно в JPEG) имеют такие дефекты

Мой метод снятия дампа на коленке имеет свои минусы и считанные данные, с первого раза, иногда, невозможно восстановить (если на шаге 24 алгоритма, расхождение d не равно нулю).

Я переписал алгоритм снятия дампа:

1. Считанные данные сразу инвертируются

2. В считанной странице на ПК сразу применяется алгоритм коррекции данных каждого из 8 секторов. Разделил это действие на 8 потоков для ускорения. 

3. Если в одном из секторов возникает невосстановимая ошибка, производится повторное чтение страницы, но коррекция производится только ошибочного сектора.

4. Если ошибка не устраняется за 128 попыток, то оставляю данные «как есть» и сохраняю в отдельный файл адреса ошибок.

На некоторых форумах я прочитал, что иногда «играют» напряжением питания микросхемы NAND.

Я подключил лабораторный источник питания и снял дампы всех ошибочных страниц на напряжениях от 1.7в до 3.6в с шагом 0.1в и это дало свои плоды, удалось скорректировать почти половину ошибок.

Вытащил все файлы, но некоторые так и не удалось восстановить: сломались от моих кривых рук, от подключения флешки после попытки запаять дорожки или за 9 лет «уплыл» заряд из плавающего затвора. Загадка.

Статья получилась достаточно большой. На проделанную работу по восстановлению данных у меня ушло около 6 месяцев и еще около 4 месяцев на написание статьи.

Всем, о чем написал в статье, занимался в свободное время в рамках саморазвития.

Спасибо за внимание.