Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 21
Текст из файла (страница 21)
Следовательно, правило обнаружения ошибок в двоичной строке совсем простое: если строка является кодовым словом, то предполагается, что она правильна; если строка не является кодовым словом, то она содержит ошибку. Структуру п-разрядного двоичного кода и предоставляемые нм возможности обнаруживать независимые ошибки легко объяснить, воспользовавшись представлением об п-мерном кубе. Код — это просто подмножество вершин п-мерного куба. Для того чтобы код обнаруживал все одиночные ошибки, никакие две вершины, соответствующие кодовым словам„не должны быть смежными.
В качестве примера на рис.2.10(а) показан 3-разрядный двоичный код, состоящий из пяти кодовых слов. Кодовое слово 111 непосредственно соседствует с кодовыми словами 1 ! О, О! 1 и 101. Так как единичный отказ мог бы преобразовать 111 в ! 10, 011 или 101, этот код не обнаруживает все одиночные ошибки. Если комбинацию 111 не считать кодовым словом, то получится код, позволяющий обнаруживать одиночные ошибки, как это показано парис.2.! 0(Ь). Никакая одиночная ошибка не может преобразовать одно кодовое слово в другое. (Ь) 110 1Ы 011 г 010,ггг 010 г 011 г' ° -- юлиее сею ° = вв кСДОВ06 СЛОВО ,+ ~100 у'101 ° ° Рис. 2.10. Кодовые слова двух различных 3-Разрядных двоичных кодов: (а) минимальное расстояние =1, обнаруживаются не все одиночные ошибки; (Ь) ыинимальное расстояние =2, обнаруживаются все одиночные ошибки Влияние неисправностей на данные предсказывают на основе моделей ошибок (вггаг тааИ).
В простейшей модели, которую мы здесь рассмотрим, таибки являются нюависимьти (Гпг!ервпдепг еггаг тоде!). Согласно этой модели предполагается, что однократная физическая неисправность может повлиять толью на один бит данных; в этом случае говорят, что искаженные данные содержат одиночную ошибку (лтя!в вггаг). Множественные неисправности могут вызватьмногакратныв таийаг (ти(пр!в вггаг), когда ошибка происходит в двух или большем числе битов, но обычно предполагается, что многократные ошибки менее вероятны, чем одиночные. 86 Глава 2.
Числовые системы и коды Способность кода обнаруживать одиночные ошибки можно сформулировать в терминах расстояний, введенных в предыдущем параграфе: Код обнаруживает все одиночные ошибки, если минимальное расстояние (тГттит г!Гтаапсе) между кодовыми словами во всех возможных парах рав- но 2. В общем случае для построения кода, обнаруживающего одиночные ошибки, с числом кодовых слов, равным 2", нам нужно и+1 битов, Первые п битов в кодовом слове, называемые инфариаиионными битами (тгогтабап Ым), могут быть любыми из 2" п-разрядных двоичных строк. Чтобы получить код с минимальным расстоянием 2, мы добавляем еще один бит, называемый контрольным битом (раг!О Ьй), которому присваиваем значение О, если число единиц среди информационных битов четно, и значение 1 в противном случае.
Иллюстрацией сказанного служат первые два столбца в табл.2.13 дяя кода с тремя информационными символами. Каждое (и+1)-разрядное двоичное кодовое слово содержит четное число 1 и такой код называется кодаи с проверкой на четкость (вива-рагпу савв). Можно также построить код, у которого каждое (и+1)-разрядное двоичное кодовое слово содержит нечетное число единиц; такой код представлен в третьем столбце табл ицы и носит название кода с проверкой на нечетнасть (одг1-рагйу соде). Эти коды иногда называют также кодами с одним кантральныл~ битам (1-Ь!г рагйу сабе).
Табл. 2.13. Коды с тремя информационными битами и минимальным расстоянием, равным 2 Инфсрмаци- Код е провер- Код с пРоверкой самые биты кой на четнссть на нечетность 000 1 001 0 000 001 000 0 001 1 010 1 010 0 010 О11 1 О!! 011 0 100 !00 1 !000 101 101 0 10! ! !100 110! 110 111 1 1!10 Коды с одним контрольным символом не обнаруживают ошибки в 2-х битах, поскольку изменение двух битов не нарушает правила четности. Если, например, изменяются трн бита в кодовом слове, то в получающейся двоичной строке правило четности нарушается, и эта строка не является кодовым словом. Правда, пользы от этого немного.
Если ошибки независимы, то ошибка в 3-х битах существенно менее вероятна, нежели ошибка в 2-х битах, которую обнаружить нельзя. Таким образом, способность кодов с одним контрольным символом обнаруживать ошибки ограничивается практически случаем ошибок в одном бите. Для обнаружения многократных ошибок можно воспользоваться другими кодам н, у которых минимальное расстояние больше 2. 2.15. Коды, обнаруживанием исправляющие ошибки 87 2.15.2. Коды, исправляющие ошибки и обнаруживающие многократные ошибки 1011000 00010!О 1001011::;;,',;:;, .'~(:~',": .„Р.,0001001 1011011,,:-' "!:;.,"!.':.." 46ОМ11::.::а"=:":):4Ф.
'":4в"'0001«1:-':1' '11 ' '1: ::., ОО!1ОО! а= ",-;4М,".;В:.1!1!ОО! 001!О!! 1010011 1010001 ° = водсвов слова 1110010 в- 10!0000 'ь)агсв ас в"' 1010110 1011010 1000010 ° = нв инавое слова Рис. 2.11. Несколько кодовых слов и слов, не являющихся кодовыми, для 7-разрядного двоичного кода с минимальным расстоянием, равным 3 Воспользовавшись большим числом проверочных бипвов (с)веск Ь1м), а не одним контрольным битом, и следуя определенным правилам, можно построить код с минимальным расстоянием больше 2. Прежде чем показать, как зто сделать, давайте посмотрим, как можно применять такой код для исправления одиночных ошибок и обнаружения многократных ошибок.
Предположим, что минимальное расстояние кода равно 3. На рис. 2.! 1 представлен фрагмент и-мерного куба для такого кода. Как видно из рисунка, между каждой парой кодовых слов имеется, по крайней мере, два кодовых слова, не являющихся кодовыми. Предположим теперь, что мы передаем кодовые слова, и пусть сбои приводят к ошибке самое большее в одном бите в каждом принятом слове.
Тогда принятое слово, не являющееся кодовым, с ошибкой в одном бите будет ближе к переданному кодовому слову, нежели к какому-либо другому кодовому слову. Поэтому в случае, когда мы принимаем слово, не являющееся кодовым, можно исправить ошибку (е««о«со««еспоп), заменив принятое слово на ближайшее кодовое слово, как это показано стрелками на рисунке. Принятие решения о том, какое слово было передано, на основе принятого слова называется декодировакиен (г)всойпЯ, а устройство, осуществляющее зто действие, называется декодером (с(ссоре«), исправляющим ошибки.
88 Глава 2. Числовые системы и коды Код, применяемый для исправления ошибок, называется коррекюирукнцим кодом (еггог-соггесйпй соде). В общем случае справелливо правило: если минимальное расстояние в коде равно 2 с +1, то с его помощью можно исправлять до с ошибок в битах (в предыдущем примере с = 1). Если минимальное расстояние кода равно 2с +Ы +1, то он позволяет исправлять до с ошибок и обнаруживать до л' ошибок в других битах. На рис.2.! 2(а) в качестве примера приведен фрагмент л-мерного куба для кода с минимальным расстоянием, равным 4 (с =1, о' =1).
Единичные ошибки в словах 00 101010 и 11010011, не являющихся кодовыми, можно исправить. Однако ошибки, приведшие к слову 10100011, исправить нельзя, поскольку это слово не может возникнуть в результате одиночной ошибки, а может лишь стать следствием искажения двух битов в одной из двух возможных пар ошибок. Таким образом, этот код позволяет обнаружить ошибку в двух битах, но не дает возможности исправить ее. Если принятое слово не является кодовым, то мы не знаем, какое именно кодовое слово в действительности было передано; мы знаем только, какое кодовое слово ближе всего к принятому. Следовательно, как показано на рис. 2.12(Ь), результат «исправления» тройной ошибки может оказаться неправильным.
Подобного рода промахи бывают допустимы, если тройные ошибки происходят с очень малой вероятностью. С другой стороны, в случае, когда тройные ошибки следует принимать во внимание., можно изменить правило декодирования данного кода. Вместо того, чтобы пытаться исправлять ошибки, будем просто воспринимать слова, не являющиеся кодовыми, как содержащие ошибки. Тогда, как показано на рис. 2.12(с), тот же самый кодс минимальным расстоянием, равным 4, позволяет обнаруживать до трех ошибок без их исправления (с =О, д =3). 2.15.3. Коды Хэмминга В 1950 году Хэмминг описал общий метод построения кодов с минимальным расстоянием, равным 3, которые теперь называют кодами Хэимкнга (Натт!ля спайз). Для произвольного ! его метод дает (2' — 1)-разрядный двоичный код с ! проверочными и 2' — 1 — 1 информационными битами.
Коды с меньшим числом информационных битов с минимальным расстоянием 3 получаются путем удаления информационных битов из кода Хэмминга с большим числом битов. Разряды в кодовом слове кода Хэмминга можно пронумеровать от 1 до 2' — 1. В этом случае, в разряде, номер которого является степенью 2, стоит проверочный бит, а в остальных разрядах помещаются информационные биты. Каждый проверочный бит вместе с некоторым подмножеством информационных битов обьеднняются в одну группу согласно проверочной матрице (рагйу-слесгг тшг!х).
Как показано на рис. 2.13(а), в группу, относящуюся к каждому проверочному биту, попадают такие информационные биты, у которых номер позиции в двоичной записи содержит 1 в том же разряде, что и номер позиции данного проверочного символа. Например, проверочный бит с номером 2 (010) объелиняется в одну группу с информационными битами с номерами 3 (О! 1), 6 (110) и 7 (111). Прн заданной комбинации значений информационных битов значение проверочного бита выбирается по правилу четности; другими словами, полное число единиц в группе с этим проверочным символом должно быть четно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
