Инструменты пользователя

Инструменты сайта


Боковая панель

Регистрация

Учебные курсы

Учебные проекты

Материалы к экзаменам

Полезная информация

Обратная связь

others:teorija_kodirovanija

Криптография — математическая дисциплина, связанная с изучением методов и средств защиты информации, обеспечивающих конфиденциальность, имитозащиту, опознавание и ряд других функций. Современная криптография, особенно криптография с открытым ключом, базируется на достаточно глубоких результатах алгебры, теории чисел и алгебраической геометрии.

Изначально криптография изучала методы шифрования информации — обратимого преобразования открытого (исходного) текста на основе секретного алгоритма и/или ключа в шифрованный текст (шифротекст). Традиционная криптография образует раздел симметричных криптосистем, в которых зашифрование и расшифрование проводится с использованием одного и того же секретного ключа. Помимо этого раздела современная криптография включает в себя асимметричные криптосистемы, системы электронной цифровой подписи (ЭЦП), хеш-функции, управление ключами, получение скрытой информации, квантовую криптографию.

Криптография не занимается: защитой от обмана, подкупа или шантажа законных абонентов, кражи ключей и других угроз информации, возникающих в защищенных системах передачи данных.

Криптография — одна из старейших наук, её история насчитывает несколько тысяч лет.

Защита информации средствами криптографии — бурно развивающаяся область прикладной науки. Если раньше криптография была уделом избранных, а ее результаты не касались рядовых граждан, то сегодня все изменилось. Роль криптографии в защите информации возрастает в связи с расширением областей ее применения, затрагивающих интересы многих людей. Например, электронная торговля через Интернет базируется на совокупности криптографических протоколов, таким образом, вопросы криптографической защиты информации приобретают повседневный практический смысл.

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

Немецкая криптомашина Lorenz использовалась во время Второй мировой войны для шифрования самых секретных сообщений

Роторная шифровальная машина Энигма, разные модификации которой использовались германскими войсками с конца 1920-х годов до конца Второй мировой войны

Современная криптография

Для современной криптографии характерно использование открытых алгоритмов шифрования, предполагающих использование вычислительных средств. Известно более десятка проверенных алгоритмов шифрования, которые при использовании ключа достаточной длины и корректной реализации алгоритма криптографически стойки.

Распространенные алгоритмы:

  1. симметричные DES, AES, ГОСТ 28147-89, Camellia, Twofish, Blowfish, IDEA, RC4 и др.;
  2. асимметричные RSA и Elgamal (Эль-Гамаль);
  3. хэш-функций MD4, MD5, MD6, SHA-1, SHA-2, ГОСТ Р 34.11-94.

Во многих странах приняты национальные стандарты шифрования. В 2001 году в США принят стандарт симметричного шифрования AES на основе алгоритма Rijndael с длиной ключа 128, 192 и 256 бит. Алгоритм AES пришёл на смену прежнему алгоритму DES, который теперь рекомендовано использовать только в режиме Triple DES. В Российской Федерации действует стандарт ГОСТ 28147-89, описывающий алгоритм блочного шифрования с длиной ключа 256 бит, а также алгоритм цифровой подписи ГОСТ Р 34.10-2001.

Код Боуза-Чоудхури-Хоккенгема

При изучении кодов Боуза-Чоудхури-Хоккенгема (короче- БЧХ-кодов) можно увидеть всю мощь приложений абстрактной алгебры и сугубо практической области, пронизывающей все стороны современной жизни. Как известно, БЧХ-коды широко используются в европейских системах передачи данных. Распространённая их разновидность позволяет передавать слова длины до 231 с помощью кодовых слов длины 255 и обнаруживать до 6, а исправлять до 3 ошибок (Биркгоф, Барти, 1976). В обосновании построения БЧХ-кодов используется следующие результаты высшей алгебры:

  1. Линейная алгебра, включая матрицы, векторы, умножение вектора на матрицу, решение систем линейных уравнений, линейную зависимость и независимость, векторные пространства, их размерность и базисы, пространства решений систем линейных уравнений, определители, включая определитель Вандермонда;
  2. Теория групп, включая группы классов вычетов, смежные классы, теорему Лагранжа, понятия абелевой группы, нормальной подгруппы, фактор-группы, конечной циклической группы;
  3. Теория колец, включая идеалы, теорему о гомоморфизмах и фактор-кольца;
  4. Теория многочленов над кольцами, включая понятия неприводимых многочленов, наименьшего общего кратного многочленов и вообще теорию делимости многочленов;
  5. Теория полей, их подполей, простых полей, расширений, алгебраических расширений, алгебраических элементов и минимальных многочленов;
  6. Теория конечных полей, фактор-кольца колец многочленов над полями вычетов по простому модулю.

Таким образом, в теории БЧХ-кодов используется весь мощный аппарат высшей и абстрактной алгебры, разработанный к середине двадцатого века. Здесь особенного внимания заслуживает тот факт, что важнейшие приложения получили теории групп, полей и их расширений, конечных полей - теории, заложенные гениальным математиком Эваристом Галуа еще в первой трети 19 века для совсем других целей - для исследования проблемы разрешимости уравнений любой степени.

ТЕОРИЯ КОДИРОВАНИЯ Теория кодирования информации является одним из разделов теоретической информатики . К основным задачам , решаемым в данном разделе , необходимо отнести следующие : р азработка принципов наиболее экономичного кодирования информации

с огласование параметров передаваемой информации с особенностями канала связи ; р азработка приемов , обеспечивающих надежность передачи информации по каналам связи , т . е . отсутствие потерь информации . Две последние задачи связаны с процессами передачи информации . Первая же задача – кодирование информации – касается не только передачи , но и обработки , и хранения информации , т . е . охватывает широкий круг проблем ; частным их решением будет представление информации в компьютере . С обсуждения этих вопросов и начнем освоение теории кодирования . Определение понятий Кодирование информации - процесс преобразования сигнала из формы , удобной для непосредственного использования информации , в форму , удобную для передачи , хранения или автоматической переработки ( Цифровое кодирование , аналоговое кодирование , таблично - символьное кодирование , числовое кодирование ). Процесс преобразования сообщения в комбинацию символов в соответствии с кодом называется кодированием , процесс восстановления сообщения из комбинации символов называется декодированием Информацию необходимо представлять в какой - либо форме , т . е . кодиров ать . их ов одного кода с символами или группами ание – перевод информации , представленной посредством первичного алфавита , в последовательность от одной формы представления информации к другой , более в одной знаковой системы в знаки другой мации из закодированного вида ученной последовательности кодов ). Шифр – код , значение и правила использования которого известно ограниченному кругу лиц . Для представления дискретной информации используется некоторый алфавит . Однако однозначное соответствие между информацией и алфавитом отсутствует . Другими словами , одна и та же информация может быть представлена посредством различных алфавитов . В связи с такой возможностью возникает проблема перехода от одного алфавита к другому , причём , такое преобразование не должно приводить к потере информации . Определение понятий Кодирование информации - процесс преобразования сигнала из формы , удобной для непосредственного использования информации , в форму , удобную для передачи , хранения или автоматической переработки ( Цифровое кодирование , аналоговое кодирование , таблично - символьное кодирование , числовое кодирование ). Процесс преобразования сообщения в комбинацию символов в соответствии с кодом называется кодированием , процесс восстановления сообщения из комбинации символов называется декодированием Информацию необходимо представлять в какой - либо форме , т . е . кодиров ать . их ов одного кода с символами или группами ание – перевод информации , представленной посредством первичного алфавита , в последовательность от одной формы представления информации к другой , более в одной знаковой системы в знаки другой мации из закодированного вида ученной последовательности кодов ). Шифр – код , значение и правила использования которого известно ограниченному кругу лиц . Для представления дискретной информации используется некоторый алфавит . Однако однозначное соответствие между информацией и алфавитом отсутствует . Другими словами , одна и та же информация может быть представлена посредством различных алфавитов . В связи с такой возможностью возникает проблема перехода от одного алфавита к другому , причём , такое преобразование не должно приводить к потере информации . Алфавит , с помощью которого представляется информация до преобразования называется первичным ; алфавит конечного представления – вторичным . Код – (1) правило , описывающее соответствие знаков или их сочетаний одного алфавита знакам или их сочетаниям другого алфавита ; - (2) знаки вторичного алфавита , используемые для представления знаков или их сочетаний первичного алфавита . Код – совокупность знаков ( символов ) и система определённых правил , при помощи которой информация может быть представлена ( закодирована ) в виде набора из таких символов для передачи , обработки и хранения . Конечная последовательность кодовых знаков называется словом . Наиболее часто для кодирования информации используют буквы , цифры , числа , знаки и их комбинации . Код – набор символов , которому приписан некоторый смысл . Код является знаковой системой , которая содержит конечное число символов : буквы алфавита , цифры , знаки препинания , знаки препинания , знаки математическ операций и т . д . Кодирование – операция отожествления символов или групп символ символов другого кода . Кодиров кодов . Кодирование информации – процесс формирования определенного представления информации . В более узком смысле под термином « кодирование » понимают переход удобной для хранения , передачи или обработки . Кодирование информации – процесс преобразования сигналов или знако знаковой системы , для использования , хранения , передачи или обработки . Декодирование - операция , обратная кодированию , т . е . восстановление инфор ( восстановление в первичном алфавите по пол Шифрование – разновидность кодирования . Кодированиеинформации . Основныепонятия . Источникпредставляетсообщениевалфавите , который называется первичным , далееэтосообщениепопадаетвустройство , преобразующееипредставляющееегово вторичном алфавите . • Код – правило , описывающеесоответствиезнаков ( илиих сочетаний ) первичногоалфавитазнаком ( ихсочетаниями ) вторичногоалфавита . • Кодирование – переводинформации , представленной сообщениемвпервичномалфавите , впоследовательность кодов . • Декодирование – операцияобратнаякодированию . • Кодер – устройство , обеспечивающеевыполнениеоперации кодирования . • Декодер – устройство , производящеедекодирование . О http://profbeckman.narod.ru/InformLekc.htm Операции кодирования и декодирования называются обратимыми , если их последовательное применение обеспечивает воз врат к исходной информации без каких - либо её потерь . Примером обратимого кодирования является представление знаков в телеграфном коде и их восстановление после передачи . Примером кодирования необратимого может служить перевод с одного естественного языка на другой – обратный перевод , вообще говоря , не восстанавливает исходного текста . Безусловно , для практических задач , связанных со знаковым представлением информации , возможность восстановления информации по ее коду является необходимым условием применения кода , поэтому в дальнейшем изложении ограничим себя рассмотрением только обратимого кодирования . Таким образом , кодирование предшествует передаче и хранению информации . При этом хранение связано с фиксацией некоторого состояния носителя информации , а передача – с изменением состояния с течением времени ( т . е . процессом ). Эти состояния или сигналы будем называть элементарными сигналами – именно их совокупность и составляет вторичный алфавит . Любой код должен обеспечивать однозначное чтение сообщения ( надежность ), так и , желательно , быть экономным ( использовать в среднем поменьше символов на сообщение ). Возможность восстановить текст означает , что в языке имеется определенная избыточность , за счет которой мы восстанавливаем отсутствующие элементы по оставшимся . Ясно , что избыточность находится в вероятностях букв и их комбинациях , их знание позволяет подобрать наиболее вероятный ответ . Компьютер может обрабатывать только информацию , представленную в числовой форме . Вся другая информация ( звуки , изображения , показания приборов и т . д .) для обработки на компьютере должна быть преобразована в числовую форму . С помощью компьютерных программ можно преобразовывать полученную информацию , в том числе - текстовую . При вводе в компьютер каждая буква кодируется определенным числом , а при выводе на внешние устройства ( экран или печать ) для восприятия человеком по этим числам строятся изображения букв . Соответствие между набором букв и числами называется кодировкой символов . Как правило , все числа в компьютере представляются с помощью нулей и единиц , т . е . словами , компьютеры работают в двоичной системе счисления , поскольку при этом устройства для их обработки получаются значительно более простыми . Кодер - программист , специализирующийся на кодировании - написании исходного кода по заданным специф икациям . Кодер - одна из двух компонент кодека ( пары кодер – декодер ). Декодер - некоторое звено , которое преобразует информацию из внешнего вида в вид , применяемый внутри узла . В программном обеспечении : модуль программы или самостоятельное приложение , которое преобразует файл или информационный поток из внешнего вида в вид , который поддерживает другое программное обеспечение . В процессе преобразования информации из одной формы представления ( знаковой системы ) в другую осуществляется кодирование . Средством кодирования служит таблица соответствия , которая устанавливает взаимно однозначное соответствие между знаками или группами знаков двух различных знаковых систем . В процессе обмена информацией часто приходится производить операции кодирования и декодирования информации . При вводе знака алфавита в компьютер путем нажатия соответствующей клавиши на клавиатуре выполняется его кодирование , т . е . преобразование в компьютерный код . При выводе знака на экран монитора или принтер происходит обратный процесс - декодирование , когда из компьютерного кода знак преобразуется в графическое изображение . Кодирование информации распадается на этапы : Математическаяпостановка задачикодирования • А - первичныйалфавит . Состоитиз N знаковсосреднейинформациейназнак I А . • В - вторичный изМ знаковсосредней информациейназнак I В . • Сообщениевпервичномалфавите содержит n знаков , азакодированное –m знаков . •I s (A)- информациявисходномсообщении , I f (B)- информациявзакодированномсообщении . 1) Определение объёма информации , подлежащей кодированию . 2) Классификация и систематизация информации . 3) Выбор системы кодирования и разработка кодовых обозначений . 4) Непосредственное кодирование . 2.2 Информация и алфавит •I S (A) ≤ I f (B) – условиеобратимостикоди рования , т . енеисчезновенияинформации . n* I (A) ≤ m* I (B) ( заменилипроиз числазнаковнасреднееинформационное содержаниезнака ). •m/n – характеризуетсреднеечислознако вторичногоалфавита , которыйиспользуется длякодированияодного знакапервичного . ОбозначимегоК ( А , В ) • К ( А , В ) ≥ I(A) / I(B) Обычно К ( А , В ) >1 • К min ( А , В )= I (A) / I (B) – минимальнаядлинна кода ведением в

Хотя естественной для органов чувств человека является аналоговая форма , универсальной все же следует считать дискретную форму представления информации с помощью некоторого набора знаков . В частности , именно таким образом представленная информация обрабатывается компьютером , передаётся по компьютерным и некоторым иным линиям связи . Сообщение - последовательность знаков алфавита . При их передаче возникает проблема распознавания нака : каким образом прочитать сообщение , т . е . по по нным сигналам установи исходную последовательность знаков первичного алфавита . В устной речи это достигается использованием различных фонем ( основных звуков разного звучания ), по которым мы и отличает знаки речи . В письменности это достигается различным начертанием букв и дальнейшим анализом написанного . Можно реализовать некоторую процедуру , посредством которой выделить из сообщения тот или иной знак . Но появление конкретного знака ( буквы ) в конкретном месте сообщения – событие случайное . Следовательно , узнавание ( отождествление ) знака требует получения некоторой порции информации . Можно связать эту информацию с самим знаком и считать , что знак несет в себе некоторое количество информации . з луче ть Алфавит [ alphabetos , от названий первых двух букв греческого А . - альфа и бета ; аналогично : азбука — от аз и буки ], совокупность графических знаков — букв ( например , латинский , русский А .) или слоговых знаков ( например , индийский А . деванагари ), расположенных в традиционно установленном порядке . Знак - соглашение ( явное или неявное ) о приписывании чему - либо ( означающему ) какого - либо определённого смысла ( означаемого ). Знак — это материально выраженная замена предметов , явлений , понятий в процессе обмена информацией в коллективе . Знаком также называют конкретный случай использования такого соглашения для передачи информации . Знак может быть составным , то есть состоять из нескольких других знаков . Буквы и слова человеческого языка являются знаками . Цифры и числа являются знаками . Наука о знаковых системах называется семиотикой . Символы ( в компьютере ) - цифры , буквы , иероглифы и т . п . Начнём с самого грубого приближения ( будем называть его нулевым ) – предположим , что появление всех знаков ( букв ) алфавита в сообщении равновероятно . Тогда для английского алфавита n e =27 ( с учетом пробела как самостоятельного знака ); для русского алфавита n r =34. Из формулы Хартли nI 2 log = (1.15) находим : I 0 (e ) =log 2 27 = 4,755 бит . I 0 (r ) =log 2 34 = 5,087 бит . Получается , что в нулевом приближении со знаком русского алфавита в среднем связано больше информации , чем со знаком английского . Например , в русской букве « а » информации больше , чем в « a » английской ! Это , безусловно , не означает , что английский язык – язык Шекспира и Диккенса – беднее , чем язык Пушкина и Достоевского . Лингвистическое богатство языка определяется количеством слов и их сочетаний , а это никак не связано с числом букв в алфавите . С точки зрения техники это означает , что сообщения из равного количества символов будет иметь разную длину ( и соответственно , время передачи ) и большими они окажутся у сообщений на русском языке . В качестве следующего ( первого ) приближения , уточняющего исходное , попробуем учесть то обстоятельство , что относительная частота , т . е . вероятность появления различных букв в тексте ( или сообщении ) различна . Рассмотрим таблицу средних частот букв для русского алфавита , в который включен также знак « пробел » для разделения слов ; с учетом неразличимости букв « е » и «ë», а также « ь » и « ъ » ( так принято в телеграфном кодировании ), получим алфавит из 32 знаков со следующими вероятностями их появления в русских текстах : ТеоремаШеннона Приотсутствиипомех . Всегдавозможентакойвариант кодированиясообщения , прикоторомсреднеечислознаков кода , приходящихсянаодинзнакпервичногоалфавита , будет сколь угодноблизкокотношениюсреднихинформацийназнак первичногоивторичногоалфавитов . Шеннономбыларассмотренаситуация , когдапри кодировании сообщениявпервичномалфавитеучитываетсяразличная вероятностьпоявлениязнаков , атакжеравнаявероятность Появления знаковвторичногоалфавита . Тогда : К min ( А , В )= I (A) / log2 M= I (A) , здесь I (A) - средняя Табл . 1 . Частота появления букв Буква Частота Буква Частота Буква Частота Буква Частота пробел 0,175 o 0,090 е , ë 0,072 а 0,062 и 0,062 т 0,053 н 0,053 с 0,045 р 0,040 в 0,038 л 0,035 к 0,028 м 0,026 д 0,025 п 0,023 у 0,021

я 0,018 ы 0,016 з 0,016 ъ , ь 0,014 б 0,014 г 0,013 ч 0,012 й 0,010 х 0,009 ж 0,007 ю 0,006 ш 0,006 ц 0,004 щ 0,003 э 0,003 ф 0,002 Для оценки информации , связанной с выбором одного знака алфавита с учётом неравной вероятности их появления в сообщении ( текстах ) можно воспользоваться формулой () ∑ = ⋅−= n i i i ApApI 1 2 log) ( (1.14) . ( Информация опыта равна среднему значению количества информации , содержащейся в каком - либо одном его исходе ). Из неё , в частности , следует , что если p i – вероятность ( относительная частота ) знака номер i данного алфавита из N знаков , то среднее количество информации , приходящейся на один знак , равно : ∑ = ⋅= n i i i ppI 1 2 log ях к ш (1.17) - формула К . Шеннона . Применение формулы (1.17) к алфавиту русского языка дает значение средней информации на знак I 1 ® = 4,36 бит , а для английского языка I 1 (e ) = 4,04 бит , для французского I 1 (l) = 3,96 бит , для немецкого I 1 (d) = 4,10 бит , для испанского I 1 (s) = 3,98 бит . Как мы видим , и для русского , и для английского языков учёт вероятностей появления букв в сообщени приводит умень ению среднего информационного содержания буквы , что , кстати , подтверждает справедливость формулы (1.7) . Несовпадение значений средне информаци для английского , французского и немецкого языков , основанных на одном алфавите , связано с тем , что частоты появления й и одинак ния предш со временем , называ б ержащееся в знаке , служит мерой затрат по его вы , гласная буква , а их в русском языке 10 и , следовательно , вероятность угадывания следующей буквы 1/10, а не 1/33. В связи с этим примем следующее определение : ТеоремаШеннона ( переформулировка ) Приотсутствиипомехсредняядлина двоичногокодаможетбытьсколь угодно близкойксреднейинформации , приходящейсяназнакпервичного алфавита . овых букв в них различаются . В рассматриваемом приближении по умолчанию предполагается , что вероятность появления любого знака в любом месте сообщения остается одинаковой и не зависит от того , какие знаки или их сочета ествуют данному . Такие сообщения называются шенноновскими ( или сообщениями без памяти ). Сообщения , в которых вероятность появления каждого отдельного знака не меняется ются шенноновскими , а порождающий их отправитель – шенноновским источником . Если сообщение является шенноновским , то набор знаков ( алфавит ) и вероятности их появления в сообщении могут считаться известными заранее . В этом случае , с одной стороны , можно предложить оптимальные способы кодирования , уменьшающие суммарную длину сообщения при передаче по каналу щения , представляющего собой последовательность сигналов , сводится к задаче распознавания знака , т . е . выявлению , какой именно знак находится в данном месте сообщения . А такая задача , как мы уже убедились в предыдущем шаге , может быть решена серией парных выборов . При этом количество информации , сод связи . С другой стороны , интерпретация соо явлению . Последующие ( второе и далее ) приближения при оценке значения информации , приходящейся на знак алфавита , строятся путем учета корреляций , т . е . связей между буквами в словах . Дело в том что в словах буквы появляются не в любых сочетаниях ; это понижает неопределенность угадывания следующей буквы после нескольких , например , в русском языке нет слов , в которых встречается сочетание щц или фъ . И напротив , после некоторых сочетаний можно с большей определенностью , чем чистый случай , судить о появлении следующей буквы , например , после распространенного сочетания пр - всегда следует Особенностивторичного алфавитаприкодировании 1. Элементарныекоды 0 и 1 могутиметь одинаковые длительности (t0 = t1) илиразные ( ≠ ). 2. Длинакодаможетбытьодинаковойдлявсех знаковпервичногоалфавита ( код равномерный ) или различной ( неравномерныйкод ) 3. Кодымогутстроитьсядляотдельногознака первичногоалфавита ( алфавитное кодирование ) или

Сообщения ( а также источники , их порождающие ), в которых существуют статистические связи ( корреляции ) между знаками или их сочетаниями , называются сообщениями ( источниками ) с памятью или марковскими сообщениями ( источниками ). Учёт в английских словах двухбуквенных сочетаний понижает среднюю информацию на знак до значения I 2 (e ) =3,32 бит , учёт трехбуквенных – до I 3 (e ) =3,10 бит . Шеннон сумел приблизительно оценить I 5 (e) 2,1 бит , I 8 (e) 1,9 бит . Аналогичные исследования для русского языка дают : I 2 ® = 3,52 бит ; I 3 (r ) = 3,01 бит . Последовательность I 0 , I 1 , I 2 … является убывающей в любом языке . Экстраполируя её на учёт бесконечного числа корреляций , можно оценить предельную информацию на знак в данном языке I ∞ , которая будет отражать минимальную неопределенность , связанную с выбором знака алфавита без учета семантических особенностей языка , в то время как I 0 является другим предельным случаем , поскольку характеризует наибольшую информацию , которая может содержаться в знаке данного алфавита . Шеннон ввел величину , которую назвал относительной избыточностью языка : 0 1 I I R ∞ −= (1.18) Избыточность является мерой бесполезно совершаемых альтернативных выборов при чтении текста . Эта величина показывает , какую долю лишней информации содержат тексты данного языка ; лишней в том отношении , что она определяется структурой самого языка и , следовательно , может быть восстановлена без явного указания в буквенном виде . Исследования Шеннона для английского языка дали значение I ∞ ≈ 1,4÷1,5 бит , что по отношению к I 0 =4,755 бит создает избыточность 0,68. Подобные оценки показывают , что и для других европейских языков , в том числе русского , избыточность составляет 60 – 70%. Это означает , что возможно почти трехкратное (!) сокращение текстов без ущерба для их содержательной стороны и выразительности . Например , телеграфные тексты делаются короче за счёт отбрасывания союзов и предлогов без ущерба для смысла ; в них же используются однозначно интерпретируемые сокращения « ЗПТ » и « ТЧК » вместо полных слов ( эти сокращения приходится использовать , поскольку знаки «.» и «,» не входят в телеграфный алфавит ). Однако такое « экономичное » представление слов снижает разборчивость языка , уменьшает возможность понимания речи при наличии шума ( а это одна из проблем передачи информации по реальным линиям связи ), а также исключает возможность локализации и исправления ошибки ( написания или передачи ) при её возникновении . Именно избыточность языка позволяет легко восстановить текст , даже если он содержит большое число ошибок или неполон . В этом смысле избыточность есть определенная страховка и гарантия разборчивости . На практике учёт корреляций в сочетаниях знаков сообщения весьма затруднителен , поскольку требует объемных статистических исследований текстов . Кроме того , корреляционные вероятности зависят от характера текстов и целого ряда иных их особенностей . По этим причинам в дальнейшем мы ограничим себя рассмотрением только шенноновских сообщений , т . е . будем учитывать различную ( априорную ) вероятность появления знаков в тексте , но не их корреляции .

Двоичная система счисления Систе ма счисле ния - символический метод записи чисел , представление чисел с помощью письменных знаков . Система счисления : даёт представления множества чисел ( целых или вещественных ); даёт каждому числу уникальное представление ( или , по крайней мере , стандартное представление ); отражает алгебраическую и арифметическую структуру чисел . Мы не будем сейчас рассматривать все существующие системы счисления , а сразу перейдём к двоичной системе , имея ввиду , что она широко применяется в практике кодирования сигналов . Двоичная система счисления - это позиционная система счисления с основанием 2. Позиционная система счисления – система счисления , в которой один и тот же числовой знак ( цифра ) в записи числа имеет различные значения в зависимости от того места ( разряда ), где он расположен . В этой системе счисления натуральные числа записываются с помощью всего лишь двух символов ( в роли которых обычно выступают цифры 0 и 1). Двоичная система используется в цифровых устройствах , т . к . является наиболее простой и соответствует требованиям : 1) Чем меньше значений существует в системе , тем проще изготовить отдельные элементы , оперирующие этими значениями . В частности , две цифры двоичной системы счисления могут быть легко представлены многими физическими явлениями : есть ток — нет тока , индукция магнитного поля больше пороговой величины или нет и т . д . 2) Чем меньше количество состояний у элемента , тем выше помехоустойчивость и тем быстрее он может работать . Например , чтобы закодировать три состояния через величину индукции магнитного поля , потребуется ввести два пороговых значения , что не будет способствовать помехоустойчивости и надёжности хранения информации . 3) Двоичная арифметика является довольно простой . Простыми являются таблицы сложения и умножения - основных действий над числами . 4) Возможно применение аппарата алгебры логики для выполнения побитовых операций над числами . В цифровой электронике одному двоичному разряду в двоичной системе счисления соответствует один двоичный логический элемент ( инвертор с логикой на входе ) с двумя состояниями ( открыт , закрыт ). 1 + 0 = 1 1 + 1 = 10 10 + 10 = 100 Таблица умножения двоичных чисел 0 • 0 = 0 0 • 1 = 0 1 • 0 = 0 1 • 1 = 1 Использование двоичной системы при измерении дюймами При указании линейных размеров в дюймах по традиции используют двоичные дроби , а не десятичные , например : 5¾ ′′ , 7 15 / 16 ′′ , 3 11 / 32 ′′ и т . д . Преобразование чисел Для преобразования из двоичной системы в десятичную используют следующую таблицу степеней основания 2: 512 256 128 64 32 1 6 8 4 2 1 Начиная с цифры 1 все цифры умножаются на два . Точка , которая стоит после 1 называется двоичной точкой . Преобразование двоичных чисел в десятичные Допустим , вам дано двоичное число 110001. Для перевода в десятичное просто запишите его справа налево как сумму по разрядам следующим образом : . Можно записать это в виде таблицы следующим образом : 512 256 128 64 32 16 8 4 2 1 1 1 0 0 0 1 +32 +16 +1 Точно так же , начиная с двоичной точки , двигайтесь справа налево . Под каждой двоичной единицей напишите её эквивалент в строчке ниже . Сложите получившиеся десятичные числа . Таким образом , двоичное число 110001 равнозначно десятичному 49. Для того , что бы преобразовывать числа из двоичной в десятичную систему данным методом , надо суммировать цифры слева - направо , умножая ранее полученный результат на основу системы ( в данном случае 2). Например , двоичное число 1011011 переводится в десятичную систему так :

́ ́ 0*2+1=1»1*2+0=2»2*2+1=5»5*2+1=11»11*2+0=22»22*2+1=45» 45*2+1=91. В десятичной системе это число будет записано как 91. Или число 101111 переводится в десятичную систему так : 0*2+1=1»1*2+0=2»2*2+1=5» 5*2+1=11» 11*2+1=23 » 23*2+1=47 То есть в десятичной системе это число будет записано как 47. Преобразование десятичных чисел к ближайшей степени двойки , не меньшей этого числа . Ниже приведена функция , возвращающая число , не меньшее аргумента , и являющееся степенью двух . unsigned int to_deg_2(unsigned int num){int i; if ( num == 1 ) return 2;for( num-=1,i=1; i < sizeof (unsigned int)*8; i*=2 ) num = num|(num»i); return num+1;} Допустим , нужно перевести число 19 в двоичное . Следует воспользоваться следующей процедурой : 19 /2 = 9 с остатком 1 9 /2 = 4 c остатком 1 4 /2 = 2 с остатком 0 2 /2 = 1 с остатком 0 1 /2 = 0 с остатком 1 Итак , мы делим каждое частное на 2 и записываем в остаток 1 или 0. Продолжать деление надо пока в делимом не будет 1. Ставим числа из остатка друг за другом , начиная с конца . В результате получаем число 19 в двоичной записи ( начиная с конца ): 10011.

others/teorija_kodirovanija.txt · Последние изменения: 2015/01/14 12:33 — 83.69.2.229