0,0
рейтинг
28 октября 2013 в 16:49

Разработка → Как «волшебство» кода коррекции ошибок, которому уже больше 50 лет, может ускорить флэш-память

Код исправления ошибок (Error Correction Code или ECC) добавляется к передаваемому сигналу и позволяет не только выявить ошибки при передаче, но и при необходимости исправить их (что в общем-то очевидно из названия), без повторного запроса данных у передатчика. Такой алгоритм работы позволяет передавать данные с постоянной скоростью, что может быть важно во многих случаях. Например, когда вы смотрите цифровое телевидение — смотреть на застывшую картинку, ожидая, пока осуществляются многократные повторные запросы данных, было бы весьма неинтересно.



В 1948 году Клод Шеннон опубликовал свою знаменитую работу о передаче информации, в которой, помимо прочего, была сформулирована теорема о передаче информации по каналу с помехами. После публикации, было разработано немало алгоритмов исправления ошибок с помощью некоторого увеличения объема передаваемых данных, но одним из часто встречающихся семейств алгоритмов, являются алгоритмы, основанные на коде с малой плотностью проверок на четность (Low-density parity-check code, LDPC-code, низкоплотностный код), получившие сейчас распространение за счет простоты реализации.



Клод Шеннон

LDPC был впервые представлен миру в стенах MIT Робертом Греем Галлагером (Robert Gray Gallager), выдающимся специалистом в области коммуникационных сетей. Произошло это в 1960 году, и LDPC опередил свое время. Компьютеры на вакуумных лампах, распространенные в то время, редко обладали мощностью достаточной, для эффективной работы с LDPC. Компьютер, способный обрабатывать такие данные в реальном времени, в те годы занимал площадь почти в 200 квадратных метров, и это автоматически делало все алгоритмы, основанные на LDPC экономически невыгодными. Поэтому, на протяжении почти 40 лет использовались более простые коды, а LDPC оставался скорее изящным теоретическим построением.



Роберт Галлагер

В середине 90-х, инженеры, работающие над алгоритмами спутниковой передачи цифрового телевидения, «стряхнули пыль» с LDPC и стали его использовать, поскольку компьютеры к тому времени стали и мощней, и меньше. К началу 2000-х годов, LDPC получает повсеместное распространение, поскольку он позволяет с большой эффективностью исправлять ошибки при высокоскоростной передаче данных в условиях высоких помех (например при сильных электромагнитных наводках). Так же распространению способствовало появление специализированных систем на чипах, использующихся в WiFi технике, жестких дисках, контроллерах SCSI и т.д., такие SoC оптимизируются под задачи, и для них вычисления, связанные с LDPC вообще не представляют проблемы. В 2003 году LDPC-код, вытеснил технологию турбо-кода, и стал частью стандарта спутниковой передачи данных для цифрового телевидения DVB-S2. Аналогичная замена произошла и в стандарте DVB-T2 для цифрового «эфирного» телевидения.

Стоит сказать, что на базе LDPC строятся очень разные решения, нет «единственно правильной» эталонной реализации. Часто решения, основанные на LDPC несовместимы между собой и код, разработанный, например, для спутникового телевидения, не может быть портирован и использован в жестких дисках. Хотя чаще всего, объединение усилий инженеров разных областей дает массу преимуществ, и LDPC «в целом» является технологией не запатентованной, разные ноу-хау и проприетарные технологии вместе с корпоративными интересами встают на пути. Чаще всего, подобное сотрудничество возможно только в пределах одной компании. В качестве примера можно привести решение для канала чтения HDD от LSI под названием TrueStore®, которое компания предлагает на протяжении уже 3 лет. После приобретения компании SandForce, инженеры LSI стали работать над алгоритмами исправления ошибок SHIELD™ для SSD контроллеров (основанными на LDPC), не существовало портов алгоритмов для работы с SSD, но знания инженерной команды, работавшей над решениями для HDD очень помогли в разработке новых алгоритмов.

Тут, разумеется, у большинства читателей возникнет вопрос: чем алгоритмы, каждый алгоритм LDPC отличается от остальных? Большинство решений LDPC начинаются как декодеры с жестким решением, то есть такой декодер работает с жестко ограниченным набором данных (чаще всего 0 и 1) и использует код коррекции ошибок при малейших отклонениях от нормы. Такое решение, конечно, позволяет эффективно обнаруживать ошибки в передаваемых данных и исправлять их, но в случае высокого уровня ошибок, что иногда случается при работе с SSD, такие алгоритмы перестают справляться с ними. Как вы помните из наших предыдущих статей, любая флеш-память подвержена росту количества ошибок в процессе эксплуатации. Этот неизбежный процесс стоит учитыавть при разработке алгоритмов корреции ошибок для SSD накопителей. Что же делать в случае роста числа ошибок?

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

В 2013 году, на саммите, посвященном флэш-памяти, проходившем в Санта-Кларе, Калифорния, LSI представили свою технологию расширенной коррекции ошибок SHIELD. Комбинируя подходы с мягким и жестким решением, DSP SHIELD предлагает ряд уникальных оптимизаций для будущих технологий Flash-памяти. Например, технология Adaptive Code Rate, позволяет менять объем, отведенный под ECC так, чтоб он занимал как можно меньше места изначально, и динамически увеличивался по мере неизбежного роста количества ошибок, характерных для SSD.



Как видите, различные решения LDPC работают очень по-разному, и предлагают разные фунции и возможности, от которых во многом будет зависеть и качество работы финального продукта.
Александр Зейников @alexzeynikov
карма
72,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (7)

  • +13
    хотелось бы про сам код чо то узнать — где магия то?
    • 0
      В Википедии есть подробная информация про сам код bit.ly/1dDt3C3
      • +1
        На вики по этой тематике крайне обзорная информация, которую чаще всего пишут студенты МФТИ в качестве семестрового задания.

        Про ускорение — непонятно, ldpc коды требуют больших длин блока для эффективной работы => чтения данных большими кусками и многоитеративного декодирования, а это замедляет работу…
        Хотелось бы услышать подробности по поводу структуры или характеристик используемых кодов. Иначе это больше похоже на сложное слово для рекламной кампании.
    • 0
      <дубликат удален>
  • 0
    Где применяется LDPC понятно, но как же это волшебство помогает исправлять ошибки? Второй топик за сегодня, не соответствующий названию
  • +3
    Да нету там магии никакой. За коммерчески успешными реализациями LDPC-кодов (жесткие диски, теперь вот флешки хотят подключать) стоит огромная рутинная работа.

    Если вкратце, то суть такова: это линейный код с разреженной матрицей (это важно, поскольку хранить на контроллерах плотную матрицу в мильён элементов не получится), причем даже разреженность обычно регулярная. Линейный — значит проверка осуществляется тупым перемножением проверочной матрицы на входной сигнал. Но поскольку при чтении обязательно вмешивается физика процесса (процессы намагничивания-размагничивания, межсимвольная интерференция, дрожание считывающей головки и пр), то обычно каждый бит (набор битов) — это не хард-значение 0\1, а некое действительное число (то самое софт-значение из статьи), т.н. log-likelihood ratio, LLR, логарифм отношения правдоподобия, это если по-русски. Вот с этими действительным значениями обычно и работают алгоритмы. Например, Витерби.

    Но со всеми плюсами у этих кодов есть один, но неприятный минус — наличие т.н. error fllor, а именно существует такая неприятная ситуация, когда при увеличении SNR сигнала ошибка не уменьшается. Правда, это ошибка настолько мала (10 в минус 20 что ли для жестких дисков, ну или где-то такие порядки), что заметить ее или просимулировать практически невозможно. И вот здесь в бой вступает тяжелая статистическая артиллерия в виде importance sampling, предложенная Коулом.

    Собственно, вся работа над этими кодами по большей части распадается на две части:
    — придумывание самого кода (порождающей\проверочной матрицы);
    — придумывание хороших алгоритмов для работы с софт-значениями LLR.
    Зачастую еще применяют дополнительное кодирование на входе кода с нужными характеристиками, а также различный интерливинг, но это уже по вкусу :)

    Вот, собственно, и вся внутренняя кухня (походите по ссылкам, если интересно), которую следует давать айтишникам, а не та рекламная простынка из поста (автор, ничего личного ;)).
    • +1
      Но со всеми плюсами у этих кодов есть один, но неприятный минус — наличие т.н. error fllor, а именно существует такая неприятная ситуация, когда при увеличении SNR сигнала ошибка не уменьшается
      Она уменьшается, только не так быстро, т.е. происходит излом но наклон и этой полки круче, чем кривая канала без кодека и кривые исправляющей способности канала с кодеком и без не пересекутся.

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

Интересные публикации