Как работает ECC (коды исправления ошибок) для пакетной коррекции ошибок (стиль дисковода)?

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

Насколько я понимаю, причина, по которой дисководы имеют ошибки, связана с дефектами поверхности диска (технические характеристики или царапины). Когда головка считывает биты данных и проходит узкую царапину, схема генерирует случайное сочетание правильных и ошибочных битовых значений за "взрыв» возможно от 1 до 64 битов. Поэтому, насколько я понимаю, цель ECC дисковода состоит в том, чтобы иметь возможность исправлять все ошибочные биты в любом случайном пакете ошибок.

Кстати, я нет естественнодумать в математикетак что, пожалуйста, неНе указывай мне на математику! Я уже потратил пару часов, пытаясь прочитать википедию о Рид-Соломоне и различных других схемах, но математика в этих статьях мне совершенно непонятна (если я не потрачу несколько недель на их изучение ... если я 'мне повезло). Кроме того, из текста я неНе думаю, что любая из этих схем применима к дисководам (но может быть к CD / DVD).

Тем не менее, я'Я опишу, что мне приснилось во сне, и попрошу кого-нибудь объяснить, как на самом деле нужно делать этот тип ECC, и насколько лучше обычные подходы. Я'Я уверен, что моя схема должна быть менее эффективной, чем техника, созданная кем-то, кто знает, что он делает, и, возможно, даже разработан, когда они не спали! Прежде чем проснуться, я пытался понять, как справиться с двумя очередями на трек, но проснулся побежденным. Поэтому я также спрашиваю, как этого добиться.

Мой ментальный образ представлял собой сектор размером 4096 байт, который я мысленно разбил на 512 блоков по 64 бита каждый (так какЯ привык думать в 64-битных порциях, и потому что яЯ предполагаю, что 64-битные пакеты ошибок достаточны для практических целей. В моем приложении каждый поток данных определенно будет от 4096 до 8192 байтов.

Мой подход состоит в том, чтобы вычислить десять 64-битных кодов ECC из 4096 байтов данных. Таким образом, моя схема ECC будет записана после того, как последние из 4096 байтов данных будут представлять собой десять 64-битных кодов == 80 байтов, что не превышает 2% служебных данных. Я'назову эти десять 64-битных кодов ECCcode0" к "code9"каждый из которых очищается от нуля перед обработкой каждого сектора. И каждую 64-битную (8-байтовую) последовательность данных я назову "кусок» из-за отсутствия лучшего термина.

code9 = XOR chunks 000 to 511 == 000 to 1FF : every chunk
code8 = XOR chunks 256 to 511 == 100 to 1FF : every chunk # with bit #8 == 1
code7 = XOR chunks 128 to 255 == 080 to 0FF : every chunk # with bit #7 == 1
        and chunks 384 to 511 == 180 to 1FF
code6 = XOR chunks 064 to 127 == 040 to 07F : every chunk # with bit #6 == 1
        and chunks 192 to 255 == 0C0 to 0FF
        and chunks 320 to 384 == 140 to 17F
        and chunks 448 to 511 == 1C0 to 1FF
code5 = XOR chunks 032 to 063 == 020 to 03F : every chunk # with bit #5 == 1
        and chunks 096 to 127 == 060 to 07F
        and chunks 160 to 191 == 0A0 to 0BF
        and chunks 224 to 255 == 0E0 to 0FF
        and chunks 288 to 319 == 120 to 13F
        and chunks 352 to 383 == 160 to 17F
        and chunks 416 to 447 == 1A0 to 1BF
        and chunks 480 to 511 == 1E0 to 1FF
code4 = XOR chunks 016 to 031 == 010 to 01F : every chunk # with bit #4 == 1
        and chunks 048 to 063 == 030 to 04F
        and chunks 080 to 095 == 050 to 07F
        and so forth
code3 = XOR chunks 008 to 015 == 008 to 00F : every chunk # with bit #3 == 1
        and chunks 024 to 031 == 018 to 01F
        and chunks 040 to 047 == 028 to 02F
        and so forth
code2 = XOR chunks 004 to 007 == 004 to 007 : every chunk # with bit #2 == 1
        and chunks 012 to 015 == 00C to 00F
        and chunks 020 to 023 == 014 to 017
        and so forth
code1 = XOR chunks 002 to 003 == 002 to 003 : every chunk # with bit #1 == 1
        and chunks 006 to 007 == 006 to 007
        and chunks 010 to 011 == 00A to 00B
        and so forth
code0 = XOR chunks 001 to 001 == 001 to 001 : every chunk # with bit #0 == 1
        and chunks 003 to 003 == 003 to 003
        and chunks 005 to 005 == 005 to 005
        and so forth

Хорошо, я должен объяснить цель этого подхода. ECC, создаваемый алгоритмом, должен каким-то образом кодировать следующую информацию:

# 1: Каково правильное состояние каждого бита (все 4 КБ == 32 КБ)?

# 2: Где в потоке 4 КБ == 32 КБ произошел пакет ошибок?

Сейчас я'Я попытаюсь объяснить, почему мой сон («кошмар») полагал, что эти десять 64-битных кодов ECC могут обнаружить любой пакет ошибок длиной до 64 бит в любом месте потока 4KB == 32Kb.

Позволять'Начнем медленно и рассмотрим простой пример. Позволять'Предполагается, что когда дисковод считывает сектор, бит № 0 в одном из 512 "ломти» был неправ == перевернут.

ECC code9 говорит нам что-нибудь? Ну, code9 - это XOR каждого 64-битного блока в секторе. Следовательно, бит № 0 кода 9 представляет собой четность бита № 0 каждого 64-битного фрагмента данных, записанных в сектор. Поэтому, когда мы читаем сектор назад, ошибка в бите № 0 ЛЮБОГО одного 64-разрядного блока данных приведет к ошибке, которую мы можем обнаружить только с помощью 64-разрядного кода 9 (нет необходимости в code8, code7 ... code0). , Если бит № 0 любого 64-битного фрагмента данных неверен, то бит № 0 кода 9 в ECC, считываемый с диска, не будет согласован с битом № 0 кода 9, который мы вычисляем по данным считывания!

Ницца! Мы обнаружили ошибку в бите № 0 некоторого 64-битного блока только с code9. Однако мы не знаем, какой из 511 блоков данных содержит ошибку в своем бите # 0.

Тот'Для чего предназначены остальные восемь кодов ECC (в некотором смысле).

Остальные восемь кодов ECC позволяют намсузить" где эта ошибка

Итак, мы спрашиваем себя, что может нам сказать code8? Хорошо, что'Совершенно очевидно! code8 рассматривает только фрагменты 256-511 (последняя половина сектора), поэтому, если ошибка бита № 0 находится где-то в фрагментах 000-255 (первая половина сектора), code8 не обнаружит никакой ошибки. Но ждать! Если мы знаем, что ошибка в бите № 0 НЕ в блоках 256-511, то она ДОЛЖНА БЫТЬ где-то в блоках 000-255 (первая половина сектора). Итак, теперь мы знаем, что ошибка где-то в куске 000-255, а не в куске 256-511. Отлично!

Теперь мы спрашиваем себя, что может нам сказать code7? Ну, из интересующего нас региона (куски 000-255), code7 проверяет только куски 128-255. Поэтому, если бит № 0 ECC code7, который мы читаем с диска, отличается от кода ECC code7, который мы вычисляем по данным чтения, мы знаем, что ошибка бита № 0 находится где-то в фрагменте 128-255. Милая! Мы снова сокращаем возможное место ошибки до половины диапазона.

Теперь, что может сказать нам code6? Как это работает, становится очевидным. Как и прежде, code6 обнаруживает ошибки только в половине области, в которой, как мы знаем, ошибка. Из области, где мы сузили ошибку до (фрагменты 128-255), code6 проверяет только вторую половину (фрагменты 192-255). Поэтому, когда мы не находим ошибку в бите № 0 кода 6, мы знаем, что ошибка бита № 0 не в блоках 192-255, и, следовательно, должна быть где-то в блоках 128-191.

Когда мы находим ошибку в бите № 0 code5, мы знаем, что ошибка должна быть где-то в кусках 160-191.

Когда мы находим ошибку в бите № 0 code4, мы знаем, что ошибка должна быть где-то в кусках 176-191.

Когда мы находим ошибку в бите № 0 кода 3, мы знаем, что ошибка должна быть где-то в кусках 184-191.

Когда мы находим НЕТ ошибки в бите № 0 кода2, мы знаем, что ошибка должна быть где-то в кусках 184-187.

Когда мы находим НЕТ ошибки в бите № 0 кода 1, мы знаем, что ошибка должна быть где-то в кусках 184-185.

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

!!!!! СДЕЛАННЫЙ !!!!!

Теперь мы точно знаем, где находится ошибка в нашем 4096-байтовом секторе - в бите № 0 64-битного блока # 185.

И кусок 185 == 0x0B9 == 0 1011 1001

Хммм. Очень интересно! Каждый нулевой бит в блоке # ошибки является кодом #, где мыне найти ошибку, и каждый бит в чанке # кода ошибки является кодом #, где мысделал найти ошибку. Это означает, что мы автоматически получаем чанк #, который содержит ошибку в процессе проверки чанков кода. Когда бит в ECC для чтения совпадает с тем же битом в ECC, который мы вычислили из данных чтения, мы генерируем 0, в противном случае мы генерируем 1 (readback-ECC XOR computed-ECC). Насколько это просто? !!!

Немного подумав, мы видим, что каждый бит # в блоках данных и ECC-блокахнезависимый, Другими словами, бит № 0 в блоках ECC проверяет бит № 0 каждого 64-битного блока данных, а бит № 1 в блоках ECC проверяет бит № 1 каждого 64-битного блока данных и т. Д. , Смежные биты в значениях ECC и порциях данных совершенно независимы друг от друга. Никакие биты ближе, чем 64-битные друг от друга, никак не взаимодействуют. Эта схема рассматривает сектор как 64 отдельных сектора, каждый только 1/64 как большой.

Ага! Это должно быть причиной того, что этот метод может обнаруживать и исправлять любой пакет битов ошибок длиной до 64 бит - потому что каждый бит совершенно независим (в блоках ECC) от любого бита, расположенного ближе, чем на 64 бита.

Тот'сидеть. По крайней мере, в моем сне это объясняет, как это работает.

Что выше не делаетОбъясните следующее (мои вопросы):

# 1: Это как пакетный ECC выполняется на дисках и т. Д.?

# 2: Если этот метод не является традиционным, является ли этот метод новым?

№ 3: Эта методика легче для программного обеспечения, чем обычные методы?

# 4: У обычных подпрограмм больше или меньше накладных расходов (1,8% для 64-битных пакетов в пакете 4K)?

# 5: Как это можно расширить, чтобы исправить два пакета?

PS: Мое приложение для ECC не связано с дисководами, но имеет схожие характеристики и требования. По крайней мере, изначально мое приложение будет делать все программно: вычислять ECC в программном обеспечении, добавлять в поток данных (пакет), отправлять поток данных (пакет), получать поток данных (пакет) и выполнять описанный выше процесс. обнаруживать и исправлять любые ошибки в потоке данных (пакете). Я полагаю, это может когда-нибудь превратиться в схемотехнику в ПЛИС, но ... не сегодня.