(926)274-88-54
Бесплатная доставка.
Бесплатная сборка.
График работы:
Ежедневно. С 8-00 до 20-00.
Почта: soft_hous@mail.ru
|
|
Звоните! (926)274-88-54 Бесплатная доставка. Бесплатная сборка. |
Ассортимент тканей График работы: Ежедневно. С 8-00 до 20-00. Почта: soft_hous@mail.ru |
  
|
Читальный зал --> Программные средства foundation (а) 010 110 - щ = кодовое слово = не кодовое слово /100 (Ь) 010 Рис. 2.10. Кодовые слова двух различных 3-разрядных двоичных кодов: (а) минимальное расстояние =1, обнаруживаются не все одиночные ошибки; (Ь) минимальное расстояние =2, обнаруживаются все одиночные ошибки Влияние неисправностей на данные предсказывают на основе моделей ошибок {error model). В простейшей модели, которую мы здесь рассмотрим, ошмб/ш являются независимыми {independent error model). Сотасно этой модели предполагается, что однократная физическая неисправность может повлиять только на один бит данных; в этом случае говорят, что искаженные данные содержат одиночную ошибку {single error). Множественные неисправности могут вызвать многократные ошибки {multiple error), когда ошибка происходит в двух или большем числе битов, но обычно предполагается, что многократные ошибки менее вероятны, чем одиночные. 2.15.1. Коды, обнаруживающие ошибки Вспомним, что согласно определению, данному в параграфе 2.10, код, состоящий из и-разрядных двоичных строк, не обязательно содержит все возможные 2 кодовых слов; это как раз тот случай, о котором сейчас пойдет речь. Код, обнаруживающий ошибки {error-detecting code), обладает тем свойством, что в результате искажения или повреждения кодового слова вероятнее всего получится двоичная строка, не являющаяся кодовым словом {noncode word). Если в системе используется код, обнаруживающий ошибки, то в ней генерируются, передаются и запоминаются только кодовые слова. Следовательно, правило обнаружения ошибок в двоичной строке совсем простое: если строка является кодовым словом, то предполагается, что она правильна; если строка не является кодовым словом, то она содержит ошибку. Структуру и-разрядного двоичного кода и предоставляемые им возможности обнаруживать независимые ошибки легко объяснить, воспользовавшись представлением об и-мерном кубе. Код - это просто подмножество вершин и-мерного куба. Для того чтобы код обнаруживал все одиночные ошибки, никакие две вершины, соответствующие кодовым словам, не должны быть смежными. В качестве примера на рис. 2.10(a) показан 3-разрядный двоичный код, состоящий из пяти кодовых слов. Кодовое слово 111 непосредственно соседствует с кодовыми словами 110,011 и 101. Так как единичный отказ мог бы преобразовать 111 в 110,011 или 101, этот код не обнаруживает все одиночные ошибки. Если комбинацию 1И не считать кодовым словом, то получится код, позволяющий обнаруживать одиночные ошибки, как это показано на рис. 2.10(b). Никакая одиночная ошибка не может преобразовать одно кодовое слово в другое. Способность кода обнаруживать одиночные ошибки можно сформулировать в терминах расстояний, введенных в предыдущем параграфе: Код обнаруживает все одиночные ошибки, если минимальное расстояние {minimum distance) между кодовыми словами во всех возможных парах равно 2. В общем случае для построения кода, обнаруживающего одиночные ошибки, с числом кодовых слов, равным 2 , нам нужно п + 1 битов. Первые п битов в кодовом слове, называемые информационными битами {information bits), могут быть любыми из 2 и-разрядных двоичных строк. Чтобы получить код с минимальным расстоянием 2, мы добавляем еще один бит, называемый контрольным битом {parity bit), которому присваиваем значение О, если число единиц среди информационных битов четно, и значение 1 в противном случае. Иллюстрацией сказанного служат первые два столбца в табл. 2.13 для кода с тремя информационными символами. Каждое ( +1 )-разрядное двоичное кодовое слово содержит четное число 1 и такой код называется кодом с проверкой на четность {even-parity code). Можно также построить код, у которого каждое (и +1)-разрядное двоичное кодовое слово содержит нечетное число единиц; такой код представлен в третьем столбце таблицы и носит название кода с проверкой на нечетность {odd-parity code). Эти коды иногда называют также кода.ми с одним контрольным бито.ы {1-bit parity code).
Табл. 2.13. Коды С тремя информационными битами и минимальным расстоянием, равным 2 Коды с одним контрольным символом не обнаруживают ошибки в 2-х битах, поскольку изменение двух битов не нарушает правила четности. Если, например, изменяются три бита в кодовом слове, то в получающейся двоичной строке правило четности нарушается, и эта строка не является кодовым словом. Правда, пользы от этого немного. Если ошибки независимы, то ошибка в 3-х битах существенно менее вероятна, нежели ошибка в 2-х битах, которую обнаружить нельзя. Таким образом, способность кодов с одним контрольным символом обнаруживать ошибки офаничивается практически случаем ошибок в одном бите. Для обнаружения многократных ошибок можно воспользоваться другими кодами, у которых минимальное расстояние больше 2. 0001010 1011000 1001011 0001001 1011011 0011001 0001011 0001111 1011001 1111001 0101011 0011011 0000011 1011101 1010011 / 1001001 1010001 0010010 1010000 1010010 1010110 = кодовое слово = не кодовое слово 1110010 1011010 1000010 Рис. 2.11. Несколько кодовых слов и слов, не являюш,ихся кодовыми, для 7-разрядного двоичного кода с минимальным расстоянием, равным 3 2.15.2. Коды, исправляющие ошибки и обнаруживающие многократные ошибки Воспользовавшись большим числом проверочных битов {check bits), а не одним контрольным битом, и следуя определенным правилам, можно построить код с минимальным расстоянием больше 2. Прежде чем показать, как это сделать, давайте посмотрим, как можно применять такой код для исправления одиночных ошибок и обнаружения многократных ошибок. Предположим, что минимальное расстояние кода равно 3. На рис. 2.11 представлен фрагмент и-мерного куба для такого кода. Как видно из рисунка, между каждой парой кодовых слов имеется, по крайней мере, два кодовых слова, не являющихся кодовыми. Предположим теперь, что мы передаем кодовые слова, и пусть сбои приводят к ошибке самое большее в одном бите в каждом принятом слове. Тогда принятое слово, не являющееся кодовым, с ошибкой в одном бите будет ближе к переданному кодовому слову, нежели к какому-либо другому кодовому слову. Поэтому в случае, когда мы принимаем слово, не являющееся кодовым, можно исправить ошибку {error correction), заменив принятое слово на ближайшее кодовое слово, как это показано стрелками на рисунке. Принятие решения о том, какое слово было передано, на основе принятого слова называется декодированием {decoding), а устройство, осуществляющее это действие, называется декодером {decoder), исправляющим ошибки. ООО «Мягкий Дом» - это Отечественный производитель мебели. Наша профильная продукция - это диваны еврокнижка. Каждый диван можем изготовить в соответствии с Вашими пожеланияи (размер, ткань и материал). Осуществляем бесплатную доставку и сборку. Звоните! Ежедневно! (926)274-88-54 Продажа и изготовление мебели. Копирование контента сайта запрещено. Авторские права защищаются адвокатской коллегией г. Москвы. |