Вы можете обнаружить один переворот с помощью всего одного дополнительного бита в сообщении любой длины (как заявлено @Daniel Wagner). Проще говоря, бит четности может указывать, является ли общее количество 1-битов нечетным или четным. Очевидно, что если число неправильных битов четное, то бит четности не будет установлен, поэтому вы не сможете обнаружить 2-битные ошибки.
Теперь, для более доступного понимания того, почему вы не можете исправить ошибки 32 байта (256 бит) с помощью всего 8 бит, пожалуйста, прочитайте о коде Хэмминга (как используется в памяти ECC). В такой схеме используются специальные биты четности с исправлением ошибок (далее называемые «четность ЕС»), которые кодируют только четность подмножества общего количества битов. Для каждых 2^m - 1 суммарных битов необходимо использовать m EC битов. Они представляют каждую возможную различную маску в соответствии с шаблоном «x бит включен, x бит выключен», где x - степень 2. Таким образом, чем больше число битов одновременно, тем лучше соотношение бит данных / четности, которое вы получаете. Например, всего 7 битов позволяют кодировать только 4 бита данных после потери 3 битов ЕС, но 31 бит могут кодировать 26 битов данных после потери 5 битов ЕС.
Теперь, чтобы действительно понять это, возможно, возьмем пример. Рассмотрим следующие наборы масок. Первые две строки должны быть прочитаны сверху вниз, указывая номер бита («Самый значимый байт», который я обозначил как MSB):
MSB LSB
| |
v v
33222222 22221111 11111100 0000000|0
10987654 32109876 54321098 7654321|0
-------- -------- -------- -------|-
1: 10101010 10101010 10101010 1010101|0
2: 11001100 11001100 11001100 1100110|0
3: 11110000 11110000 11110000 1111000|0
4: 11111111 00000000 11111111 0000000|0
5: 11111111 11111111 00000000 0000000|0
Первое, на что следует обратить внимание, это то, что двоичные значения от 0 до 31 представлены в каждом столбце, идущем справа налево (чтение битов в строках с 1 по 5). Это означает, что каждый вертикальный столбец отличается друг от друга (важная часть). Я поместил вертикальную дополнительную строку между номерами битов 0 и 1 по определенной причине: столбец 0 бесполезен, поскольку в нем не установлены биты.
Чтобы выполнить исправление ошибок, мы поразрядно-И получим биты данных с предопределенной маской каждого бита EC, а затем сравним полученную четность с битом EC. Для любых вычисленных четностей, обнаруженных как несоответствующие, найдите столбец, в котором только установлены эти биты. Например, если исправляющие ошибки биты 1, 4 и 5 ошибочны при расчете по полученному значению данных, тогда столбец № 25, содержащий только 1 в этих масках, должен быть неправильным битом и может быть исправлен путем его переворачивания , Если неправильный только один бит исправления ошибок, то ошибка находится в этом бите исправления ошибок. Вот аналогия, чтобы помочь понять, почему это работает:
Есть 32 идентичных ящика, один из которых содержит мрамор. Ваша задача - найти мрамор, используя только весы в старом стиле (тип с двумя сбалансированными платформами для сравнения веса различных объектов), и вам разрешено только 5 попыток взвешивания. Решение довольно простое: вы кладете по 16 коробок с каждой стороны шкалы, а более тяжелая сторона указывает, на какой стороне находится мрамор. Отбрасывая 16 коробок на более легкой стороне, вы затем взвешиваете 8 и 8 коробок, удерживая более тяжелые, затем 4 и 4, затем 2 и 2, и, наконец, определяете местонахождение мрамора, сравнивая веса последних 2 коробок 1: 1: самые тяжелые коробка содержит мрамор. Вы выполнили задание всего за 5 взвешиваний из 32, 16, 8, 4 и 2 коробок.
Аналогично, наши битовые комбинации разделили блоки на 5 разных групп. Если вернуться назад, пятый бит EC определяет, будет ли ошибка на левой или правой стороне. В нашем сценарии с битом 25 это неверно, поэтому мы знаем, что бит ошибки находится на левой стороне группы (биты 16-31). В нашей следующей маске для бита № 4 EC (все еще с шагом назад) мы рассмотрим только биты 16-31, и мы обнаружим, что «более тяжелая» сторона снова левая, поэтому мы сузили биты 24–31. Следуя по дереву решений вниз и каждый раз сокращая число возможных столбцов пополам, к моменту, когда мы достигаем 1-го бита EC, остается только 1 возможный бит - наш «шарик в коробке».
Примечание: аналогия полезна, хотя и не идеальна: 1-бит не представлен шариками - местоположение ошибочного бита представлено мрамором.
Теперь, когда кто-то поиграет с этими масками и подумает, как устроить вещи, обнаружит, что есть проблема: если мы попытаемся создать все 31-битные биты данных, то нам потребуется еще 5 бит для EC. Но как тогда мы узнаем, что биты EC сами ошибочны? Один неверный бит EC неверно скажет нам, что некоторые биты данных нуждаются в исправлении, и мы ошибочно перевернем этот бит данных. Биты EC должны как-то кодировать для себя! Решение состоит в том, чтобы разместить биты четности внутри данных, в столбцах из приведенных выше битовых комбинаций, где установлен только один бит. Таким образом, любой бит данных, являющийся неправильным, приведет к тому, что два EC-бита будут неправильными, что делает так, что, если только один бит EC неправильный, мы знаем, что он сам по себе неправильный, а не означает, что бит данных неверен , Столбцы, которые удовлетворяют однобитному условию, это 1, 2, 4, 8 и 16. Биты данных будут чередоваться между ними, начиная с позиции 2. (Помните, мы не используем позицию 0, поскольку она никогда не предоставит никакой информации - ни один из наших битов EC не будет установлен вообще).
Наконец, добавление еще одного бита для общей четности позволит обнаруживать 2-битные ошибки и надежно исправлять 1-битные ошибки, так как мы можем затем сравнить биты EC с ним: если биты EC говорят что-то не так, но четность бит говорит иначе, мы знаем, что есть 2 неправильных бита и не можем выполнить коррекцию. Мы можем использовать отброшенный бит № 0 в качестве нашего бита четности! Фактически, теперь мы кодируем следующий шаблон:
0: 11111111 11111111 11111111 11111111
Это дает нам в итоге 6 битов проверки и исправления ошибок (ECC). Расширение схемы использования разных масок до бесконечности выглядит так:
32 bits - 6 ECC bits = 26 data
64 bits - 7 ECC bits = 57 data
128 bits - 8 ECC bits = 120 data
256 bits - 9 ECC bits = 247 data
512 bits - 10 ECC bits = 502 data
Теперь, если мы уверены, что получим только 1-битную ошибку, мы можем обойтись без бита четности # 0, поэтому имеем следующее:
31 bits - 5 ECC bits = 26 data
63 bits - 6 ECC bits = 57 data
127 bits - 7 ECC bits = 120 data
255 bits - 8 ECC bits = 247 data
511 bits - 9 ECC bits = 502 data
Это не изменится, потому что мы больше не получаем бит данных. К сожалению! 32 байта (256 бит) по вашему запросу не могут быть исправлены с помощью одного байта, , даже если мы знаем, что в худшем случае мы можем иметь только 1-битную ошибку, и мы знаем, что биты ECC будут правильными (что позволяет нам перемещать их из области данных и использовать их все для данных). Нам нужно на ДВУХ больше битов, чем у нас есть - нужно перейти к следующему диапазону 512 бит, а затем пропустить 246 бит данных, чтобы получить наши 256 бит данных. Так что это еще один бит ECC И еще один бит данных (поскольку у нас есть только 255, именно то, что сказал вам Даниэль).
Сводка :: Вам нужно 33 байта + 1 бит, чтобы определить, какой бит перевернулся в первых 32 байтах.
Примечание: если вы собираетесь отправлять 64 байта, то у вас соотношение 32: 1, так как вы можете исправить ошибку всего за 10 бит. Но дело в том, что в реальных приложениях «размер кадра» вашего ECC не может продолжать расти бесконечно по нескольким причинам: 1) Количество одновременно обрабатываемых битов может быть намного меньше размера кадра, что приводит к грубая неэффективность (вспомним ECC RAM). 2) Возможность точного исправления бита становится все меньше и меньше, поскольку чем больше кадр, тем больше вероятность того, что у него будет больше ошибок, а 2 ошибки лишают возможности исправления ошибок, в то время как 3 или более могут побеждать даже ошибку способность обнаружения. 3) Как только обнаружена ошибка, чем больше размер кадра, тем больше размер поврежденного фрагмента, который необходимо передать повторно.