Программирование NAND для чайников. Часть 1. Ошибки

Программирование NAND для чайников.
Часть 1. Ошибки.

Просмотров:(894) 4.89 (9) Оценки, комментарии

2021-02-11 Дата последнего изменения: 2021-02-28

В статье в предельно доступной форме рассматриваются особенности применения микросхем NAND FLASH.

CОДЕРЖАНИЕ:

NAND не совсем обычные микросхемы, поэтому те инженеры, которые с ними сталкиваются впервые, часто бывают обескуражены. Более подробно, хотя и очень примитивно, особенности NAND описаны в статьях "Программирование NAND FLASH" и "Программирование SPI NAND".

Здесь же я постараюсь изложить суть использования NAND еще проще.

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

1. Коварство NAND. Структура.

NAND организованы следующим образом: страницы > блоки –> логические модули –> кристаллы.

На рисунке ниже показан типичный пример организации микросхемы NAND с одним логическим модулем и одним кристаллом.

структура NAND?

В чем коварство NAND? В адресации.

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

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

При считывании NAND всегда происходит чтение всей страницы целиком, страница перемещается во внутренний буфер (page register), а уже из буфера можно прочитать содержимое страницы байт за байтом или в произвольном порядке.

То же самое при записи — сначала заполняется внутренний буфер (целиком или частично), затем страница записывается целиком. Размер буфера равен размеру страницы. Коварство адресации в том, что размер страницы не кратен степени двух. То есть просматривать содержимое микросхемы байт за байтом не получится.

2. Коварство NAND. Ошибки.

При работе микросхемы NAND возникновение ошибок — это норма. "Как так? Как можно работать с такой микросхемой?!" — скажете вы. Как можно работать с такой памятью? Способы есть, но об этом позже, а сейчас о типичном заблуждении начинающих:

Спокойно, дружище, спокойно. Это NAND, она так работает.

Сейчас типичная страница наиболее распространенных NAND равна двум килобайтам плюс дополнительные байты. Очень многие микросхемы при чтении дают до 16-ти одиночных ошибок на одну страницу. И это нормально. Берем, например, микросхему на 2 гигабайта. Нехитрое вычисление. Получаем, что при считывании микросхемы может быть до 16 777 216 ошибок!

Еще раз: 16 миллионов! Ошибок в микросхеме! Как с этим жить?! Как может что-то работать вообще? Об этом поговорим чуть позже.

А сейчас поясним понятие "одиночные ошибки".

"Одиночная ошибка" — это не одна единственная ошибка на страницу или микросхему, это ошибка в одном бите. Таких ошибок может быть много, вопреки слову "одиночная". Применительно к памяти такие ошибки правильнее было бы называть однобитными, но термин "одиночный" пришёл из теории передачи данных по линиям связи, где ошибки выявляют и исправляют такими же способами, что и в NAND.

3. Магия ЕСС.

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

ЕСС — это более продвинутый код. Он позволяет не только обнаружить но и исправить (!) ошибку в данных. Поэтому он и называется ECC (Error Correction Code) — Код Исправляющий Ошибки.

Как работает такой код? Ох, лучше не спрашивайте. Я сам не понимаю (шутка). Просто поверьте в магию. Страница считана с ошибками, но код ЕСС может все исправить. Задействуем код ЕСС — и все читается без ошибок.

Кратко опишем как выглядит работа кодера/декодера ЕСС:

Вот до этого места коды CRC и ECC не сильно отличаются, магия ЕСС начинается дальше:

Вот и вся магия. Мы просто исправляем ошибки.

Конечно код ЕСС не может исправить все ошибки. Он может исправить их небольшое количество, скажем 16. Но нам больше и не нужно! Микросхема ведь не делает много ошибок :)

4. Коварство NAND. Магия ЕСС есть, но она не работает.

"Так просто?" — скажете вы. "Тогда почему программатор не использует ЕСС для исправления ошибок?! Я из раза в раз читаю микросхему и все время ошибки".

Да. Действительно, почему?

А вот почему.
Чтобы исправить все ошибки нужно знать:

Как? Вы это не знаете?! Вот и мы не знаем. И, возможно, никто, кроме разработчика прибора, не знает.

5. Почему алгоритмов расчета ECC так много.

На данный момент самые распространённые коды исправляющие ошибки это:

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

Большинство современных встроенных систем базируются на Linux. Linux для работы накопителей на основе FLASH памяти, как правило, использует драйвер MTD. В драйвере MTD реализовано программное кодирование для NAND кодом BCH с вполне известным набором полиномов. Всё будто просто, но в реальной жизни (в реальных прошивках) такое кодирование не встречается. Почему? Всё упирается в деньги. Вернее, в желание производителей аппаратуры их сэкономить.

Почему вместо обычной памяти FLASH, работающей безошибочно, используются NAND, производящие кучу ошибок? Потому что это в разы дешевле. За разработку алгоритма кодирования/декодирования ЕСС заплатить нужно ОДИН раз, за память без ошибок нужно платить КАЖДЫЙ раз в КАЖДОМ устройстве.

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

Поэтому декодированием ЕСС в современных системах занимаются специальные сопроцессоры или контроллеры. Придумываются и реализуются более совершенные коды ЕСС. Часто используются комбинированные коды CRC/ECC. Код CRC рассчитывается быстрее, чем ЕСС, это позволяет использовать CRC-часть для обнаружения ошибок, а полное декодирование ЕСС — только при их наличии.

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

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

6. Коварство NAND. Магия ЕСС есть, но она не работает. Что делать?

Очень часто нам приходится слышать один и тот же вопрос: "Что делать, если NAND всегда читается с огромным количеством ошибок? Как прочитать без ошибок?"

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

Вы не знаете алгоритм? Тогда есть только один способ: толерантность к ошибкам (и этот способ успешно работает).

Просто читаете микросхему. Она будет считана с ошибками. При верификации требуется задать допустимое количество ошибок на страницу микросхемы. (Для всех вновь добавленных микросхем значение по умолчанию уже задано. Если не задано нужно смотреть документацию или просить нас, чтобы мы внесли данные ЕСС в базу).

Программа будет сверять микросхему и подсчитывать количество ошибок. Если количество ошибок не превысит заданное значение — значит всё в порядке. Ошибка сравнения не будет выдана, вы просто будете проинформированы о количестве "исправимых" ошибок.

Но не все так однозначно.

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

Понятно, что пример несколько искусственный, но на нём проще объяснить.

Случай 1:Запись эталона в NAND

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

Если вы эту микросхему NAND поставите в ваш прибор, он исправно заработает, поскольку встроенный в прибор алгоритм ЕСС обязан(!) исправлять не менее 4-х ошибок на страницу (это паспортные характеристики данной NAND и прибор просто обязан справляться с таким количеством ошибок).

Случай 2:Чтение микросхемы NAND

Мы считали прошивку из исправной микросхемы, стоящей в приборе (напомню, мы получаем по 3 ошибки на страницу). Далее мы еще раз считывали прошивку. Мы опять получили 3 ошибки на страницу.

Но ошибки не возникают в одних и тех же местах! При сравнении результатов 1-го и 2-го считывания может получиться до 6-ти ошибок на страницу. Это превысит допустимые 4 для данной микросхемы, но это вовсе не означает, что микросхема неисправна!

Случай 3:Копирование микросхемы NAND

Мы считали прошивку из исправной микросхемы, стоящей в приборе (получая по 3 ошибки на страницу). Далее записали полученную прошивку в чистую микросхему.

При верификации получим по 3 ошибки на страницу. Это вроде бы меньше 4-х. Но заработает ли прибор? Не факт. Всего ошибок может быть до 6-ти на страницу (3 при считывании образца плюс 3 при работе микросхемы в приборе), но ЕСС прибора исправит только 4.

На самом деле, в реальной жизни, количество ошибок по страницам в микросхемах сильно колеблется. В новых микросхемах количество ошибок не превышает одной-двух, да и то не на каждой странице. Заявленное число ошибок (в нашем примере 4) это уже в сильно изношенной микросхеме. Беда только в том, что в ремонт с формулировкой "слетела прошивка" именно такие приборы и попадают.

7. Практический совет по выбору порога ошибок.

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

Случай 1. Очень оптимистичный. У вас есть эталонная прошивка и она точно без ошибок.

Такую прошивку можно писать и верифицировать с порогом ошибок, заданным в документации на микросхему (во всех наших примерах – это 4).

Случай 2. Реальный. У вас нет эталонной прошивки.

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

При соблюдении этих условий прибор заработает с очень высокой вероятностью (ЕСС прибора должно исправить 2+2=4 ошибки).

Чем больше вы ошибок получаете при считывании эталона и верификации записи, тем меньше вероятность того, что алгоритм ЕСС справится с исправлением ошибок и прибор заработает. Здесь уже как повезет. :)

8. "Ваш программатор полный отстой, вот другие программаторы решают эту проблему".

Нет. У других производителей программаторов (во всяком случае у всех, которые нам известны на данный момент) всё точно так же. Те же предложения: "Cкажите какой ЕСС и мы все реализуем".

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

9. "Я все прочитал и ничего не понял.
Вы сможете наконец что-то сделать, чтобы NAND читались "нормально"?"

Мы над этим работаем. До сих пор мы не оставляем надежды на создание способа автоматического восстановления алгоритма ЕСС (хакинга) только на основании анализа прошивки.

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

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

Всё что нас интересует — это название микросхемы, из которой прошивка считана. Для лучшей защиты своих интересов вы можете прислать прошивку не полностью. Если вы опасаетесь — не присылайте. Это только просьба.

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

Собрав достаточную базу прошивок, я надеюсь, нам удастся "хакнуть" ЕСС и сильно облегчить вам работу с NAND.

Только совместными усилиями мы сможем добиться значительных результатов в работе!

4.89 (9)

Начальные сведения о помехозащищенном кодировании на основе кода Хэмминга

Помехозащищенное кодирование применяется для надёжной передачи данных по каналу связи, в котором может присутствовать источник помех. В МК 1986ВЕ8Т в качестве таких каналов связи выступают шины, осуществляющие передачу данных как между внутренними блоками МК, например, внутренняя память – ядро, так и между внутренними и внешними блоками, например, внешняя память – ядро. Само помехозащищенное кодирование, а также декодирование с коррекцией ошибок, осуществляется на аппаратном уровне с помощью специальных блоков. В качестве используемого самокорректирующегося кода применяется код Хэмминга, при этом в МК используется всего два вида кодовых слов: (7,4) для задания режима работы и (72,64) для внутренней памяти и памяти на внешней шине.

Общий алгоритм генерации ECC и коррекции ошибок на основе кода Хэмминга

Общий алгоритм коррекции ошибок (ECC), основанный на коде Хэмминга, на примере операции записи/чтения:

Начальная информация о коррекции ошибок на основе кода Хэмминга 7,4

Здесь мы рассмотрим построение кода Хэмминга 7,4, чтобы понять, как производится генерация ECC и коррекция одиночных ошибок.

Однако, прежде чем мы приступим к рассмотрению кода Хэмминга (7,4), сделаем небольшое отступление и рассмотрим задачу о надёжной передаче данных в ненадёжном канале связи и разберёмся, откуда появилось условие для кода Хэмминга 2 k >=k+m+1.

Небольшое отступление

Предположим, что мы хотим передать слово B= по каналу связи, в котором действует источник помех (не такая уж и гипотетическая задача). Предположим, что при передаче слова В источник помех может вызвать ошибку не более чем в 1 бите. Передавать слово В в исходном виде дело совершенно не надёжное, и установить, что же в итоге мы хотели передать, будет невозможно. Один из тривиальных способов защиты информации в данном канале: утроить все биты исходного слова (а-ля троированная логика) В’=. Тогда, если при передаче изменится один из битов, то по схеме мажорирования (по принципу большинства), можно восстановить слово В’, а значит, и исходное слово В. Такое решение при передаче данных является некорректным, так как утроение бит приведёт к тому, что в таком длинном слове вероятность появления двойных ошибок резко возрастёт, а исправить их уже не получится. Поэтому необходимо закодировать исходное слово так, чтобы увеличение его длины было минимальным.

Это как раз и сделал Ричард Хэмминг. Он рассмотрел случай, когда при передаче может возникнуть 1 ошибка, и пришёл к выводу, что, передавая закодированное слова длины l = m+k, где m – длина исходного слова, k – длина контрольных бит. Приёмник, с учётом одной ошибки, может получить l+1 различных вариантов передаваемого слова. Например, предаём слово C= длиной 3 бита. До приёмника могут дойти следующие слова:

Итого l+1=4 различных варианта принятого слова. Чтобы закодировать с помощью контрольных бит все эти случаи, необходимо чтобы 2 k >=l+1 или 2 k >= m+k+1. Вот так и появилось знаменитое неравенство для нахождения количества контрольных бит k в зависимости от необходимого количества бит m исходного слова.

Для надёжной передачи 4 бит информации (m), исходя из выше указанного неравенства, необходимо к ним добавить ещё 3 проверочных бита (k).

В обозначении 7,4 первое число (7) определяет количество бит закодированного слова, второе (4) – количество бит исходного слова.

Вычисление проверочных разрядов r[2:0] выполняется по формулам:

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

Для математического описания кодирования и декодирования исходных слов вводят специальные матрицы: матрицу G генерации и матрицу H проверки.

Матрица генерации G формирует закодированное слово путём перемножения слова A и матрицы генерации G.

X = AG, при этом операция суммирования производится по модулю 2.

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

 Перемножение вектора А на матрицу В

При перемножении матриц для кодирования Хэмминга вместо «+» используется ⊕.

Матрица G для кода 7,4 выглядит следующим образом:

 Матрица генерации для кода Хэмминга 7,4

Операция перемножения A на G:

 Перемножение вектора А на матрицу G

Таким образом перемножив A на G мы получим закодированное слово X, состоящее из слова A и проверочных бит r[2:0].

При чтении закодированного слова X заново выполняется расчёт контрольных бит на основе слова А, а затем вычисленные и считанные контрольные биты складываются по модулю 2. Результат сложения образует так называемый синдром S = . По синдрому определяется ошибка, если таковая была.

S2 = r2 ⊕ r2’ = r2 ⊕ a3 ⊕ a2 ⊕ a1 ;

S1 = r1 ⊕ r1’ = r1 ⊕ a3 ⊕ a2 ⊕ a0 ;

S0 = r0 ⊕ r0’ = r0 ⊕ a3 ⊕ a1 ⊕ a0 ;

где r[2:0]’ – заново вычисленные проверочные биты на основе считанного слова А.

Для расчёта синдрома S[2:0], аналогично матрицы генерации G, вводят проверочную матрица H. Синдром формируется путём перемножения считанного слова X и транспонированной проверочной матрицы H T :

Проверочная матрица H для кода Хэмминга 7,4 имеет вид:

 Проверочная матрица для кода Хэмминга 7,4 (S2,S1,S0)

Каждая строка этой таблицы при побитом перемножении на слово X образует соответствующий бит синдрома.

Если поменять местами строки 1 и 3, то получим проверочную матрицу, указанную в спецификации, при этом изменится порядок следования бит синдрома S = :

 Проверочная матрица для кода Хэмминга 7,4 (S0,S1,S2)

Операция перемножения X на H T (H матрица как в спецификации):

 Перемножение вектора X на матрицу H

По получившемуся вектору синдрома и проверочной матрице H можно определить, где произошла ошибка. Если ошибки не было, то синдром равен 0: S = (0, 0, 0). Если же произошла одиночная ошибка, то совпадающий с синдромом столбец указывает на ошибочный бит:

 Проверочная матрица для кода Хэмминга 7,4 (S0,S1,S2)

К сожалению, данный код Хэмминга (7,4) может применяться только в условиях возникновения однократных ошибок. Если произойдет две и более ошибки, то отличить их от одинарной не получится, а поэтому в данном случае исправление одной ошибки не приведёт к восстановлению исходного слова.

Чтобы этого избежать, вводят дополнительный бит четности p (parity), с помощью которого можно определить, произошла одиночная ошибка либо двойная и более. Тогда, если имеет место однократная ошибка, слово можно исправить, если двукратная – слово восстановлению не подлежит.

Бит чётности может занимать любую позицию в закодированном слове, но для определённости мы сделаем, как указано в спецификации, и добавим его на место 4 бита. При этом закодированное слово X приобретёт вид:

Бит чётности p вычисляется на основе всех остальных бит слова X путём их сложения по модулю 2:

При определении ошибки заново вычисляется бит чётности p’ и складывается со считанным битом p, при это данный результат будет являться новым битом синдрома. Так как мы добавили бит чётности на 0 позицию проверочных бит, то слово синдрома S = приобретёт следующий вид:

S0 = p ⊕ p’ = p + r2 ⊕ r1 ⊕ r0 ⊕ a3 ⊕ a2 ⊕ a1 ⊕ a0 ;

S1 = r0 ⊕ r0’ = r0 ⊕ a3 ⊕ a1 ⊕ a0 ;

S2 = r1 ⊕ r1’ = r1 ⊕ a3 ⊕ a2 ⊕ a0 ;

S3 = r2 ⊕ r2’ = r2 ⊕ a3 ⊕ a2 ⊕ a1 ;

С учётом бита чётности проверочная матрица H будет иметь вид:

 Проверочная матрица для кода Хэмминга 7,4 c битом чётности (S1,S2,S3,S0)

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

 Проверочная матрица для кода Хэмминга 7,4 c битом чётности (S1,S2,S3,S0)

Для кода Хэмминга (72,64) генерации ECC и коррекция ошибок осуществляется точно таким же образом, просто используемые матрицы немного больше. Надо заметить, что для кода (72, 64) расстояние Хэмминга позволяет определять двойные ошибки, а потому бит чётности в данном коде не используется.

Программная генерация ECC

В спецификации приведён пример программного вычисления проверочных бит ЕСС для кода Хэмминга (72, 64). Как уже было отмечено ранее, в данном коде не используется бит чётности, поэтому алгоритм вычисления ECC для кода (7,4) с битом чётности будет отличаться от алгоритма для кода (72,64). В связи с этим мы разберём здесь программную реализацию вычисления ECC для кода (7,4) c битом чётности на примере вычисления бит CFGx в режимах запуска EXTBUS_CFG+JB и EXTBUS_CFG+JA.

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

Полный код функции представлен ниже:

Разберём основные части.

Для начала составим из правой части проверочной матрицы H массив генерации ECC G[], при этом каждый элемент данного массива будет представлять строку правой части матрицы H. Далее в цикле формируем проверочные биты, путем выборки необходимые информационные биты, а именно, накладывая маску из массива генерации, после чего суммируем их по модулю два. Делаем это для трёх проверочных бит. Дописываем их к информационным битам. После вычисляем бит чётности p суммированием по модулю два всех проверочных и информационных бит, и дописываем его в кодируемое слово. Исходное слово закодировано.

Источники:

https://www. chipstar. ru/articles/nand-dlya-chaynikov/

https://startmilandr. ru/doku. php/prog:spec:hammingcode? do=export_xhtml

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: