Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 133
Текст из файла (страница 133)
° УПРАЖНЕНИЯ 1. Воспользовавшись грамматикой из примера 17.32, постройте дерево грамма- тического разбора для строки аЬЬЬ. 2. Воспользовавшись грамматикой из примера 17.33, постройте дерево грамма- тического разбора для строки ааа6ЬЬ. 3. Воспользовавшись грамматикой из примера !7.34, постройте дерево грамма- тического разбора для строки ЬаЬааЬ. 4. Найдите язык, порожденный грамматикой Г = (Ас, Т, В, Р), определенной с помощью Аг = (В, А, В), Т = (а,Ь) и заданного множества продукций Р: Я вЂ” ~АВ, А — ~аА, А — ~Л,  — +ВЬ,  — ~Л.
5. Найдите язык, порожденный грамматикой Г = ()т',Т,В,Р), определенной с помощью АГ = (В, А,В), Т = (а,6) и заданного множества продукций Р; В- аВ, В-~ЬА, А — ~аВ, В- Ь. 6. Найдите язык, порожденный грамматикой Г = (Х,Т,В,Р), определенной с помощью Х = (В, А, В), Т = (а, 6) и заданного множества продукций Р: 5 — ~аА,  — +аА, В- ЬВ, А- аВ,  — +ЬВ, А — ~ЬА,  — ~6, А — ~а. 752 ГПАВА ЗТ. Теория вычислений 7. Найдите язык, порожденный грамматикой Г = (Ю,Т,Я,Р), определенной с помощью М = (Я, А, ВТ, Т = (а, ЬТ и заданного множества продукций Р: Я- С, А — +аВ, С вЂ” ~ЬС, В- ЬВ, С вЂ” аА,  — + аА, А — ~ ЬА, В -+ Л.
754 ГЛАВА 1В. Теория кодов ставляют один символ передаваемого сообщения. Блоковый код особенно полезен при ограничении длины кода для каждого посланного символа или буквы. Другим способом построения однозначно декодируемого кода является использование префиксного кода, который рассматривался в разделе, посвященном взвешенным деревьям. Согласно определению 17.!О, код С является префиксным, если обладает тем свойством, что элемент кода не может быть начальной строкой другого элемента кода. Таким образом, при чтении строки из единиц и нулей, изображающей символ А, всегда известен момент завершения строки.
Префиксный код называют также мгновенным кодом. Разновидностью префиксного кода является кома-код. При его использовании каждый символ кодируется строкой из единиц, в конце которой стоит нуль. Значит, множество строк кода имеет вид (0,10,110,11110,111110,...). Этот код имеет явный недостаток: элементы кода могут быть очень длинными и занимать большой объем памяти. Часто необходимо сжимать данные, чтобы минимизировать объем памяти для их хранения или время для передачи данных. Что касается минимизации объема памяти, то наиболее эффективным является код Хаффмана. Кодирование при помощи кода Хаффмана описано в разделе 15.3.
Преимущество кода Хаффмана состоит также в том, что это мгновенный код. Хорошо известным примером кода, минимизирующего время передачи, является код Морзе. В кодах Хаффмана и Морзе буквы или символы, которые встречаются наиболее часто, имеют более короткий код. В коде Морзе буквы разделены "пробелами", а слова — тремя "пробелами".
В данном случае "пробелы" — это единицы времени. В процессе передачи данных могут возникать ошибки. Все, что может стать причиной ошибок, называется неопределенным термином "шум". Например, данные, полученные от такого отдаленного космического корабля, как "Чоуадег" или "Па!!!ео", наверняка подвержены различного рода шумам. В некоторых случаях интерес представляет только определение наличия ошибки, что соответствует ситуации передачи данных еще раз. Коды, обладающие свойством определения наличия ошибок, называются кодами, обнаруживающими ошибки.
В другом случае, когда данные не могут быть переданы еще раз (например, данные от удаленного космического корабля), требуется дополнительная инфор- РАДЕЛ 18.1. Введение 755 мация о данных с целью не только обнаружения, но и исправления ошибки. Коды, позволяюшие исправлять ошибки, называются кодами, исправляющими ошибки.
Может показаться разумным всегда использовать коды с исправлением ошибок. Проблема использования кодов с исправлением ошибок и кодов с обнаружением ошибок состоит в том, что они должны включать в себя дополнительную информацию, поэтому они являются менее эффективными в отношении минимизации объема памяти. К сожалению, использование кодов с исправлением ошибок и кодов с обнаружением ошибок не дает абсолютной гарантии того, что ошибка будет исправлена или обнаружена. Проблема заключается в возможности многих ошибок.
Несомненно, ошибку можно исправить или обнаружить, если она одна. Все, что мы можем сделать, — это уменьшить вероятность того, что ошибки останутся необнаруженными и неисправленными. Но проблема, опять-таки, в том, что чем в большей степени будет уменьшена эта вероятность, тем больше информации потребуется переслать, и тем менее эффективным будет наш код. Прежде чем начать изучение кодов с исправлением ошибок и кодов с обнаружением ошибок, необходимо ввести еше один тип кодов. Существует классический пример, демонстрирующий применение такого кода.
Предположим, имеется врашаюшийся диск, разделенный на секторы, и серия щеток или лазерных лучей, выделяюших информацию о скорости вращения диска. Если двоичные строки, записывающие нумерацию соседних секторов, существенно различаются в отдельных цифрах при переходе от одного сектора к следующему, тогда считывающее устройство воспримет это так, чтобы измененный сектор мог выработать число, совершенно отличное от числа, выработанного любым из секторов.
В данном случае желательно пронумеровать секторы таким образом, чтобы двоичные строки, определяюшие соседние секторы, различались только одной цифрой. Код, обладающий таким свойством, называется кодом Грея. Его построению посвящен раздел 6.7. В качестве первого метода обнаружения ошибок рассмотрим бит контроля четности. Продемонстрируем этот метод на примере кода АСС!1. АСС!1-код является блоковым кодом, который использует 7 битов, поэтому любой закодированный символ изображается строкой из семи символов 1 и О. Восьмой бит добавляется таким образом, чтобы количество единиц было четным. Поэтому, если код переданной строки получен с единственной ошибкой, то количество единиц будет нечетным, и получатель информации поймет, что произошла ошибка. К сожалению, если произошло две ошибки, их нельзя будет обнаружить, поскольку количество единиц опять будет четным.
Предположим, что вероятность ошибки при передаче равна 0.01 как для изменения 1 на О, так и для изменения 0 на 1. Предположим далее, что вероятность ошибки не зависит от расположения ошибки и от того, что является ошибкой: изменение 1 на 0 или наоборот. Предположим также, что появление одной ошибки не влияет на вероятность появления другой. Из биномиальной теоремы для вероятности (теорема 8.10!) известно, что вероятность появления в точности одной ошибки равна (з)(.01)(.99)т, что приблизительно равно 0.07. Вероятность же появления в точности двух ошибок равна (~~)(.01)з(.99)е, что приблизительно равно 0.002 и является сушественно меньшей величиной.
75Б ГЛАВА 18. Теория кодов Код АЗСК с битом контроля четности символ БР символ № 3 % й г РЕ!. Поскольку 3 ошибки будут обнаружены, вероятность не обнаружить более двух ошибок меньше, чем вероятность наличия четырех или более ошибок, поскольку любое нечетное количество ошибок будет обнаружено.
Эта вероятность пренебрежимо мала по сравнению с вероятностью одной или менее ошибок. Рассмотрим код, в котором для кодирования используется простое повторение кодируемой строки заданное число раз. Например, если при кодировании каждую строку кода нужно повторить один раз, то 10110 будет закодировано как 1011010110. Если при кодировании каждую строку кода нужно повторить дважды, то 10110 будет закодировано как 101101011010110. Если при кодировании каждая строка повторена один раз, то в результате получаем код с обнаружением код 00000000 10000001 10000010 00000011 10000100 00000101 00000110 10000111 10001000 00001001 00001010 10001011 00001100 10001101 10001110 00001111 10010000 00010001 00010010 10010011 00010100 10010101 10010110 00010111 00011000 10011001 10011010 10011011 10011100 00011101 00011110 10011111 символ Ы !Л. БОН БТХ ЕТХ ЕОТ ЕЫЯ АСК ВЕ1.
ВБ НТ 1Г НТ ГГ Сй БО Б! Р!.Е РС1 РС2 РСЗ РС4 ЫАК БУХ ЕТВ САН ЕМ ЯЗВ ЕБС ГБ ОБ ВБ УБ код 10100000 00100001 00100010 10100011 00100100 10100101 10100110 00100111 00101000 10101001 10101010 00101011 10101100 00101101 00101110 10101111 00110000 10110001 10110010 00110011 10110100 00110101 00110110 10110111 10111000 00111001 00111010 10111011 00111100 10111101 10111110 00111111 код 11000000 01000001 01000010 11000011 01000100 11000101 11000110 01000111 01001000 11001001 11001010 01001011 11001100 01001101 01001110 11001111 01010000 11010001 11010010 01010011 11010100 01010101 01010110 11010111 11011000 01011001 01011010 11011011 01011100 11011101 11011110 01011111 символ А В С Р Е Г О Н ! .! К М Ы О Р Я й Б Т Ч % Х У Е [ код 01100000 11100001 11100010 01100011 11100100 01100101 01100110 11100111 11101000 01101001 01101010 11101011 01101100 11101101 11101110 01101111 11110000 01110001 01110010 11110011 01110100 11110101 11110110 01110111 01111000 11111001 11111010 01111011 11111100 01111101 01111110 11111111 а Ь с е К Ь ! ! ! гп п о Р г! г 5 ! н т х У х рдЗДЕЛ 1В.2.
Порождающие матрицы 757 ошибок. Если произошла ошибка, то соответствующие позиции не будут совпадать. Например, если закодированная строка имеет вид 111111010110111011, то ошибки имеются в третьем и в последнем битах. Исправить ошибки мы не можем, поскольку не знаем, в какой из копий какая ошибка присутствует. Если кодируемая строка повторяется дважды, то лучше всего выявить ошибку. Если имеются три копии строки, то можно исправить код при наличии единственной ошибки. Если имеется отличие в битах в соответствующих позициях строк, то выбирается значение, которое встречается дважды.
Например, если строка имеет длину 4 и нам передано 110110011101, то во второй позиции мы два раза получим 1 и один раз О. Таким образом, предполагаем, что правильное значение равно 1, и правильным вариантом закодированной строки является 1101. Конечно, если ошибка появляется в одной и той же позиции строки более одного раза, возникает проблема. Если строка повторена так, что имеется и ее копий, то исправление ошибки дает правильный результат, если при повторении ошибка встречается в одной и той же позиции менее, чем Я~ раз. 18.2. ПОРОЖДАЮЩИЕ МАТРИЦЫ С этого момента мы будем предполагать, что все строки кода имеют фиксированную длину п, и будем трактовать эти строки как векторы или (1 х п)-матрицы. Следовательно, можно использовать сложение векторов.
Мы, однако, определим сложение по модулю 2, так что 1+ 1 = О. Таким образом, 11110001 + 10100111 = 01010110. Коды, представленные в данном разделе, называются линейны.чи кодами. Они известны также как групповые коды. Как уже упоминалось, строками кода С будут двоичные строки длины и, которые мы будем рассматривать также как векторы или (1 х и)-матрицы. Если В„ — множество всех двоичных строк длины и, то С вЂ” подмножество множества В„. Предлагаем читателю доказать, что множество В„вместе с указанной выше операцией сложения образует группу относительно сложения. Каждая строка из В„совпадает со своим обратным элементом, так что в этом смысле сложение и вычитание — это одно и то же. Если в некоторых ситуациях покажется, что следует вычитать, а не складывать, то нужно помнить, что это не имеет значения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
