Научная литература
booksshare.net -> Добавить материал -> Физика -> Аветисян Р.Д. -> "Теоретические основы информатики" -> 21

Теоретические основы информатики - Аветисян Р.Д.

Аветисян Р.Д., Аветисян Д.О. Теоретические основы информатики — Телеком , 2003. — 170 c.
Скачать (прямая ссылка): teoriticheskieosnoviinformatiki2003.pdf
Предыдущая << 1 .. 15 16 17 18 19 20 < 21 > 22 23 24 25 26 27 .. 64 >> Следующая


Возникает вопрос: а всегда ли, при любом числе информационных символов мы смогли бы поступать аналогичным образом? Нет, не смогли бы, если по-прежнему хотим, чтобы двоичный набор символов ех-2'-- > ei) указывал на адрес ошибки. Потому что уже когда число контрольных символов больше трех, мы не имеем права взять в качестве контрольных последние X символов. Легко убедиться, что при этом контрольная матрица непременно оказалась бы вырожденной, т.е. значение ее детерминанта оказалась' бы равным нулю. Более того, даже в рассмотренном нами случае, когда число контрольных символов равно трем, мы не смогли бы в качестве контрольных взять, например, первые три символа. Во всех этих случаях определители контрольных матриц (вспомним, что столбцы этой матрицы суть двоичные записи номеров выбранных нами контрольных символов) оказываются равными нулю. Пусть, например, мы выбрали в качестве контрольных не пачку символов ?5, ?fi, ?7, а символы ?,, ?2, ?3. Тогда нам пришлось бы иметь дело с квадратной матрицей третьего порядка, столбцы которой являются двоичными формами записи чисел 1, 2 и 3:

C =

1 0 1 О 1 1 ООО

Равенство нулю детерминанта этой матрицы свидетельствует о том, что систему (2.146) + (2.166) нельзя решить относительно переменных ?b?2H?3.

53

ГЛАВА 1 Таким образом, при выборе среди т + л символов д контрольных следует заботиться о том, чтобы определитель контрольной матрицы порядка л, столбцы которой представляют собой двоичные записи номеров выбранных символов, не оказался равным нулю. Именно чтобы избавиться от этих забот, Р. Хэмминг рекомендует в качестве контрольных взять символы с индексами 1, 2. 4, 8 и т.д. Легко обнаружить, что при гаком выборе контрольных символов мы всегда (независимо от их числа) будем иметь дело с единичной матрицей.

Кроме зависимости (2.10а), на рис. 2.4 приведена также зависимость относительной избыточности (5//ср )• 100% от т. Легко заметить, что с увеличением т требуемый процент избыточности для обнаружения и исправления одиночной ошибки резко уменьшается. Столь неестественный результат является следствием искусственного, далекого от реальности допущения, что в рамках каждого кодового набора независимо от его длины in + х может произойти не более одной ошибки. Если же допустить возможность двух и более ошибок, то задача их обнаружения, и тем более исправления усложняется. Построить для этих случаев коды столь же элегантные, как код Р. Хэмминга для одиночной ошибки, пока не удалось.

В заключение подытожим те основные результаты, которые при двоичном кодировании текстов предствляются наиболее важными и будут использованы в последующих главах. В общем случае, когда значения вероятностей появления различных букв алфавита в исходном тексте зависят от того, какие буквы им предшествовали, значение энтропии H вычисляется по формуле (2.9). Если же такая зависимос ть отсутствует, то значение энтропии H определяется по более простой формуле (2.3). Формула вычисления энтропии еще более упрощается и принимает вид (2.3а), если к тому же имеет место P (i) = P (/') = 1 /п. При заданном значении H среднее число двоичных символов, приходящихся на одну букву исходного текста, всегда (при любом методе кодирования) больше или равно Н. Знак равенства достигается лишь при оптимальном кодировании текста, т.е. при максимальном его сжатии, когда избыточность доводится до нуля и каждый двоичный символ закодированного текста предельно загружен - содержит один бит информации. При этом появления в закодированном тексте символов "0" и "1" равновероятны и не зависят от того, какие символы им предшествовали.

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

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

ЛИТЕРАТУРА К ГЛАВЕ 2

1. Аршином MH . СадонскиЛ /I.E. Коды и математика. - M.: Наука. 1983.

2. Бауэр Ф.. Гoo.i Г. Информатика. - M.: Мир, 1976.

3. Шеннон К Работы гю теории информации и кибернетике. - M.: Изд-во ии. лит.

1963. ПЕРЕДАЧА ТЕКСТОВ ПО КАНАЛАМ

< СВЯЗИ. ПРОПУСКНАЯ

CQ СПОСОБНОСТЬ КАНАЛОВ СВЯЗИ

<

с;

В УСЛОВИЯХ параллельного функционирования целого ряда информационно-вычислительных центров (ИВЦ) страны, находящихся в различных стадиях внедрения и эксплуатации, вопросы, связанные с оптимальной организацией обмена информацией между ними, приобретают характер первостепенной важности. Сложилась ситуация, когда информационная изоляция, пусть даже подкрепленная какими-то внутрисистемными преимуществами данного ИВЦ, чревата опасностью его замораживания. Наряду с традиционными методами в настоящее время широко практикуется обмен информацией на машиночитаемых носителях.
Предыдущая << 1 .. 15 16 17 18 19 20 < 21 > 22 23 24 25 26 27 .. 64 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed