Восстановление поврежденных битов с использованием данных четности - PullRequest
0 голосов
/ 02 декабря 2011

Вот головоломка!

Допустим, у нас есть 64 байта, каждый байт составляет восемь битов плюс один бит четности

Допустим, есть еще один контрольный байт LRC (образованныйпобитовый XOR (все 64 байта)

Таким образом, мы можем визуализировать это как сетку 8 + 1 на 64 * 1

Если один бит поврежден, проверка четности помечает его: одна строкане выполнит проверку четности, а также один столбец.

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

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

Но это очень маловероятный сценарий.

Мой вопрос: как мне поступить с ремонтомнабор данных таким образом?насколько возможно восстановление?

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

Ответы [ 3 ]

1 голос
/ 12 апреля 2013

64 байта, каждый байт составляет восемь битов плюс один бит четности Контрольный байт LRC (формируется битовым XOR со всеми 64 байтами) 64 + 8 байтов будут использоваться как 1 бит четности на байтовое слово. поэтому каждый блок будет иметь 64 данных + 9 байт четности

LRC сообщит вам, что блок плох, если бит не является битом четности в блоке (большое предположение.) Вы можете посчитать эмпатию, поскольку знаете, что байт плохой, вы можете использовать грубую силу нескольких разных битов для исправления как lrc, так и байта, пока оба не совпадут, но поскольку один lrc только говорит вам, что у вас есть шанс 1/256 получить комбинацию который соответствует вам, вы получите набор математических данных, который соответствует критерию как «фиксированный»

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

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

Если вы решите сделать это, я бы рекомендовал начать с блокирования 50 байтов данных на 64 блока. это оставляет вам 14 байтов четности для реализации математической модели. Значение 14/64 близко к 16/64, или 1/4 байтов, задействованных в блоке, предназначены только для целей спасения.

1/4 вашего набора данных будет потеряно, но некоторая стабильность получена. в вашем примере 9/71 это около 13% данных.

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

например, если у вас есть файл в 1 мегабайт, и вы говорите, что ваша эмпатия в отношении вашего паритета повреждена в 4 областях. Это MP4-файл или zip-файл, так сильно поврежденный.

Если урон ограничен 1 битом на блок, и вы, скорее всего, можете восстановить файл. если вы скажете 2 бита на блок, вы будете знать, что 2 области на блок были повреждены, что дало последовательность из 8 квадратов к возможным файлам. Вы можете сгенерировать 64 файла и попытаться разархивировать каждый, но, скажем, урон составляет 3 бита на блок, теперь вы можете смотреть на 8 кубов.

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

0 голосов
/ 12 апреля 2013

2-мерное восстановление четности с одним битом на столбец или строку не поддается ремонту, просто обнаруживается.

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

Посмотрите, может быть, вики raid 5 и raid 6 архитектуры. они используют методы, аналогичные секторам, распределенным между приводами.

0 голосов
/ 02 декабря 2011

Полагаю, вы имели в виду сетку 8 + 1 на 64 + 1.

Предположим, один из битов без проверки четности поврежден.Бит четности байта данных помечает этот байт.Четность на всех байтах помечает столбец (бит), который был поврежден.Все хорошо.

Предположим, что один из битов четности "обычных" байтов данных поврежден.Последний бит дополнительного байта четности пометит его, нет?

Предположим, один из битов четности байта четности поврежден.Последний бит байта дополнительной четности пометит его, не так ли?

Так как же определяется значение этого бита?

...