Как работает ECC для пакетной коррекции ошибок?
Как работает 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-битных кодов ECC от "code0" до "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 в программном обеспечении, добавлять к потоку данных (пакету), отправлять поток данных (пакет), получать поток данных (пакет) и выполнять описанный выше процесс. обнаруживать и исправлять любые ошибки в потоке данных (пакете). Я полагаю, что это может когда-нибудь превратиться в схемотехнику в ПЛИС, но... не сегодня.