Помехоустойчивое кодирование

Избыточное кодирование информации. Код Хэмминга.

12345

При контроле передачи информации наибольшее распространение получили методы информационной избыточности, использующие коды с обнаружением и коррекцией ошибок.

Если длина кода n разрядов, то таким двоичным кодом можно представить максимум 2^n различных слов. Если все разряды слова служат для представления информации, код называется простым (неизбыточным). Коды, в которых лишь часть кодовых слов используется для представления информации, называются избыточными. Часть слов в избыточных кодах является запрещенной, и появление таких слов при передаче информации свидетельствует о наличии ошибки.

Коды разделяются на равномерные и неравномерные. В равномерных кодах все слова содержат одинаковое число разрядов. В неравномерных кодах число разрядов в словах может быть различным. В вычислительных машинах применяются преимущественно равномерные коды.

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

Способность кода обнаруживать или исправлять “ошибки” определяется так называемым минимальным кодовым расстоянием. Кодовым расстоянием между двумя словами называется число разрядов, в которых символы слов не совпадают. Если длина слова п, то кодовое расстояние может принимать значения от 1 до n. Минимальным кодовым расстоянием данного кода называется минимальное расстояние между двумя любыми словами в этом коде. Если имеется хотя бы одна пара слов, отличающихся друг от друга только в одном разряде, то минимальное расстояние данного кода равно 1.

Простой (не избыточный) код имеет минимальное расстояние dmin — 1. Для избыточных кодов dmin > 1. Если dmin > 2, то любые два слова в данном коде отличаются не менее чем в двух разрядах, следовательно, любая одиночная ошибка приведет к появлению запрещенного слова и может быть обнаружена. Если dmin = 3, то любая одиночная ошибка создает запрещенное слово, отличающееся от правильного в одном разряде, а от любого другого разрешенного слова — в двух разрядах. Заменяя запрещенное слово ближайшим к нему (в смысле кодового расстояния) разрешенным словом, можно исправить одиночную ошибку.

В общем случае, чтобы избыточный код позволял обнаруживать ошибки кратностью r, должно выполняться условие:

dmin>r+1

Код Хэмминга.

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

где d — размер блока данных в битах, p — количество необходимых контрольных бит. Обычно для характеристики кода Хэмминга используют пару (c, d), где с — длина передавемого блока данных с контрольными битами, а d — чистая длина данных. Например, (11, 7) означает, что передаваемая длина данных — 7 бит, количество контрольных бит равно 4, что составляет общую длину блока 11 бит. В отличае от других методов коррекции ошибки, где контрольные биты дописываются в конец или начало блока данных (либо вообще в другом пакете данных), биты кода Хэмминга записываются вместе с данными в строго определённых позициях. Здесь и делее мы будем нумеровать биты не с нуля, а с единицы. Тогда позиции в которых записываются контрольные биты соответствуют степеням двойки (2k, k = 0, 1, 2, …), то есть 1, 2, 4, 8 и т.д.
Рассмотрим механизм работы кода Хэмминга на примере передачи 7-битового кода 1110011. Для контроля целостности блока данных такой длины, нам необходимо 4 бита кода Хэмминга, которые записываются в позициях 1, 2, 4, 8:

Позиция бита
Значение бита * * * *

Таблица 1 — Расположение битов кода Хэмминга (отмечены ‘*’)

Контрольная сумма формируется путем выполнения операции "исключающее ИЛИ" над кодами позиций ненулевых битов. В данном случае это 11, 10, 9, 5 и 3.

Таблица 2 — Нахождение контрольной суммы

Полученная контрольная сумма записывается в соответствующие разряды блока данных — младший бит в младший разряд. Таким образом формируется следующий блок данных:

Позиция бита
Значение бита

Таблица 3 — Результирующий блок данных

Просуммировав коды позиций с ненулевыми битами получаем 0, что является признаком корректного блока данных.

Таблица 4 — Проверка корректности блока данных

Теперь рассмотрим два случая ошибки: 1) ошибка в бите 7 — бит 0 заменён на бит 1 и 2) ошибка в бите 5 — бит 1 заменён на бит 0. Просуммируем коды позиций с ненулевыми битами:

 
 
 
 
 
 
 
 
 
сумма   сумма

Таблица 5 — Контрольная сумма в блоках данных содержащих ошибку

В обоих случаях контрольная сумма равна позиции бита, переданного с ошибкой. Теперь для исправления ошибки достаточно инвертировать бит, номер которого указан в контрольной сумме.

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

Задача поиска подстроки в строке заключается в нахождении в оригинальной строке, точного вхождения (соответствие всех символов) подстроки. В результате программа должна выдать номера символов всех вхождений подстроки…

Метод Грубой силы.

Этот алгоритм заключается в проверке всех позиций текста с 0 по n – m (n-длина строки, m-длина подстроки) на предмет совпадения с началом образца. Если совпадает — смотрим следующую букву и т.д.

Алгоритм грубой силы не нуждается в предварительной обработке и дополнительном пространстве.

Оптимизацией метода грубой силы является алгоритм хэш функции…

Хэш-функции

Хэш-функция — это преобразование, получающее из данных произвольной длины некое значение фиксированной длины. Простейшими примерами являются контрольные суммы. Бывают криптографические и программистские хэши. Криптографический хэш отличается от программистского следующими двумя свойствами: необратимостью и свободностью от коллизий. Обозначим m — исходные данные, h(m) — хэш от них. Необратимость означает, что если известно число h0, то трудно подобрать m такое, что h(m) = h0. Свободность от коллизий означает, что трудно подобрать такие m1 и m2, что m1!= m2, но h(m1) = h(m2).
Криптографические хэш-функции разделяются на два класса:
— хэш-функции без ключа
— хэш-функции с ключом.

Хэш-функции без ключа разделяются на два подкласса:
— слабые хэш-функции,
— сильные хэш-функции.
Слабой хэш-функцией называется односторонняя функция H(x), удовлетворяющая следующим условиям:
1) аргумент х может быть строкой бит произвольной длины;
2) значение H(x) должно быть строкой бит фиксированной длины;
3) значение H(x) легко вычислить;
4) для любого фиксированного x вычислительно невозможно найти другой x’!= x, такой что H(x’)=H(x).
Пара x’ != x, когда H(x’)=H(x) называется коллизией хэш-функции. Сильной хэш-функцией называется односторонняя функция H(x), удовлетворяющая условиям 1-3 для слабой хэш-функции и свойству 4′:
4′) вычислительно невозможно найти любую пару x’ != x, такой что H(x’)=H(x).
Поскольку из свойств 1-2 следует, что множество определения хэш-функции значительно шире множества значений, то коллизии должны существовать. Свойство 4 требует, чтобы найти их для заданного значения х было практически невозможно. Требование 4′ говорит о том, что у сильной хэш-функции вычислительно невозможно вообще найти какую-либо коллизию.

Хэш-функцией с ключом называется функция H(k,x) удовлетворяющая свойствами:
1) аргумент х функции H(k,x) может быть строкой бит произвольной длины;
2) значение H(k,x) должно быть строкой бит фиксированной длины;
3) при любых k и x легко вычислить H(k,x);
4) для любого х должно быть трудно вычислить H(k,x) не зная k;
5) должно быть трудно определить k даже при большом числе неизвестных пар {x, H(k,x)} при выбранном наборе х или вычислить по этой информации H(k,x’) для x’ != x.

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

Кроме того, удобно, например, пароли в базе хранить не в открытом виде, а в хэшированном.

Вот некоторые алгоритмы хэш-функций:
MD2
Автор: FIXME!
Размер: 128 бит.

MD4
Автор: Р.Райвест (R. Rivest).
Размер: 128 бит.

MD5. Капитально переделанный MD4.
Автор: Р.Райвест (R. Rivest).
Размер: 128 бит.

SHA.
Один из (относительно) новых алгоритмов свертки.
Автор: FIXME!
Размер: 160 бит.

ГОСТ Р34.11-94
Российский алгоритм.

Размерность получаемого значения очень удобна для формирования по паролю ключа для ГОСТ 28147-89.
Автор: FIXME!
Размер: 256 бит.

Рассмотрим поиск подстроки в строке с помощью хэш-функции. Каждый символ имеет свой уникальный код от 0 до 255. Суть метода заключается в том, чтобы для подстроки подсчитать некоторую хэш-функцию (например, сумму кодов всех символов в строке), затем посчитать ту же самую хэш-функцию для части строки, равной по длине подстроке, и, в случае совпадения хэш-функции, полностью сравнить его. Ускорение работы алгоритма связано с тем, что мы каждый раз не пересчитываем каждый раз хэш-функцию, а только отнимаем значение функции от самого "старого" символа и добавляем значение функции от следующего символа.

12345



Оценка достигаемой надежности. При определении требований к надежности необходимо учитывать: назначение и функции АСУ ТП и ее подсистем; условия и режим функционирования АСУ ТП; временные особенности работы управляемого объекта (частота поступающих возмущений, продолжительность смены, продолжительность и периодичность плановых остановок технологического процесса для проведения текущих и капитальных ремонтов оборудования и т. п.); надежность технологических объектов, необходимость и возможность ручного управления технологическим объектом; виды и возможные последствия отказов функций (подсистем, АСУ ТП в целом-), достигнутый уровень надежности аналогичных систем; возможные пути повышения и обеспечения надежности АСУ ТП.

Требования, предъявляемые к надежности АСУ ТП, а также методы оценки и (или) контроля уровня надежности АСУ ТП на различных стадиях создания системы должны быть указаны в техническом задании, техническом и рабочем проектах АСУ ТП, где должны быть приведены необходимые обоснования и расчеты надежности системы.

Оценку надежности АСУ ТП проводят с учетом надежности только технических средств АСУ ТП; надежности технических средств, особенностей программ и алгоритмов; надежности технических средств, особенностей программ и алгоритмов, а также действий оперативного персонала.

Оценку надежности АСУ ТП при ее проектировании (с целью прогноза ожида-еьюго уровня надежности) можно проводить аналитическими методами, методами статистического моделирования илн комбинированными методами.

Проектная оценка надежности АСУ ТП с учетом надежности только технических средств, осуществляемая, как правило, на начальных этапах проектирования системы, является ориентировочной и используется для предварительного определения состава комплекса технических средств и структур АСУ ТП.

Проектная оценка надежности АСУ ТП с учетом надежности технических средств системы и особенностей реализуемых алгоритмов и программ осуществляется, как правило, при разработке технического и программного обеспечения системы. Эту оценку используют, в частности, для выбора комплекса технических средств АСУ ТП, структуры программ и алгоритмов управления, способов алгоритмического и программного контроля н защиты от ошибок.

Проектная оценка надежности АСУ ТП с учетом надежности технических средств системы, особенностей алгоритмов и программ, а также действий оперативного персонала осуществляется, как правило, на завершающих этапах проектирования АСУ ТП для важнейших функций системы. Эту оценку используют для уточнения состава комплекса технических средств, структур и функций АСУ ТП, алгоритмов и программ управления процессом, инструкций для оперативного персонала системы, а также для определения требований к подготовке и квалификации оперативного персонала.

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

Пути повышения надежности. Традиционный путь — резервирование, т. е. метод повышения надежности объекта введением избыточности, под которой понимают дополнительные средства или возможности сверх минимально необходимых для выполнения объектом заданных функций. Для повышения надежности АСУ ТП применяют структурное (использование избыточных структурных элементов), временное (использование избыточного времени), информационное (использование избыточной информации), функциональное (использо- ванне особенности элементов выполнять дополнительные функции) резервирование, вводят алгоритмическую" избыточность, используют системы диагностики состояния оборудовання, строят АСУ по иерархическому принципу, предусматривают использование человека в контуре управления при отказе технических средств (эргатиче-ская избыточность).

Информационная избыточность в АСУ ТП может быть введена путем использова. ния избыточных датчиков, а также представления обрабатываемой информации в корректирующем коде (с обнаружением нли исправлением ошибок), что при реализации приводит к аппаратурной или временной избыточности.

Временная избыточность обусловлена увеличением времени вычислений (на повторный счет н т. п.) и используется при введении других видов избыточности для исправления ошибок в алгоритме функционирования.

Аппаратурная избыточность — это различные виды резервирования оборудования, введение специальных схем контроля и диагностики, ЗИП и т. п.

Алгоритмическая избыточность используется в различных формах. Наиболее простой метод — дублирование, т. е. повторение- решения частей задачи или всей целиком со сравнением результатов, совпадение которых подтверждает правильность решения, а несовпадение инициирует повторение расчета.

Недостатки метода — существенное увеличение времени решения задачи, исправление только случайных ошибок. Метод «усеченного» алгоритма, который примерно на порядок короче (по времени выполнения), чем основной, состоит в быстром получении грубой оценки результата для последующего сравнения с результатом вычислений по полному алгоритму; Несмотря на то что метод незначительно увеличивает затраты времени процессора, его применение ограничено тем, что не для каждого алгоритма удается построить су-" щественно усеченный вариант.

По методу подстановки в исходные уравнения корней, найденных при. решении, решение признается правильным, если разность правой и левой части уравнения не выходит за заданные пределы. Такой кон- троль требует значительно меньше време- ни, чем повторение решения, и при том обнаруживает не только случайные, но и систематические ошибки, пропускаемые при-повторении решения.

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

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


⇐ Предыдущая12345678910Следующая ⇒


Дата публикования: 2015-01-25; Прочитано: 234 | Нарушение авторского права страницы



studopedia.org — Студопедия.Орг — 2014-2018 год.(0.001 с)…

ASCII – путеводитель для новичков

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

Что это такое?

ASCII представляет собой кодировочную таблицу печатных символов (см. скриншот №1), набираемых на компьютерной клавиатуре, для передачи информации и некоторых кодов. Иными словами происходит кодирование алфавита и десятичных цифр в соответствующие символы, представляющие и несущие в себе необходимую информацию.

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

Для решения подобных вопросов были разработаны другие версии таблицы ASCII. Например, для языков с иноязычной структурой были или убраны буквы английского алфавита, или к ним добавлялись дополнительные символы в виде национального алфавита. Так, в кодировке ASCII могут присутствовать русские буквы для национального использования (см. скриншот №2).

Где применяется система кодировки ASCII?

Данная кодировочная система необходима не только для набора текстовой информации на клавиатуре. Она также используется в графике. Например, в программе ASCII Art Maker графические изображения различных расширений состоят из спектра символов кодировки ASCII (см. скриншот №3).

Как правило, подобные программы можно разделить на те, что выполняют функцию графических редакторов, инвертируя изображение в текст, и на те, что конвертируют изображение в ASCII-графику. Всем известный смайлик (или как его еще называют «улыбающееся человеческое лицо») тоже является примером кодировочного символа.

Данный метод кодировки также может быть востребован во время написания или создания документа HTML. Например, вы вводите определённый и необходимый вам набор знаков, а при просмотре самой страницы на экран будет выведен символ, соответствующий данному коду.

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

Если читатель непосредственно связан с информационно-коммуникативными технологиями (ИКТ), то ему будет полезно ознакомиться и с такими системами как:

  1. Переносимый набор символов;
  2. Управляющие символы;
  3. EBCDIC;
  4. VISCII;
  5. YUSCII;
  6. Юникод;
  7. ASCII art;
  8. КОИ-8.

Свойства таблицы ASCII

Как и любая систематизированная программа, ASCII обладает своими характерными свойствами. Так, например, десятеричная система исчисления (цифры от 0 до 9) преобразуется в двоичную систему исчисления (т.е. каждая десятеричная цифра преобразуется в двоичную 288=1001000 соответственно).

Буквы, располагающиеся в верхних и нижних колонках, отличаются друг от друга лишь битом, что существенно снижает уровень сложности проверки и редактирование регистра.

При всех этих свойствах кодировка ASCII работает как восьми битная, хотя изначально предусматривалась как семи битная.

Применение ASCII в программах Microsoft Office:

В случае необходимости данный вариант кодирования информации может быть использован в Microsoft Notepad и Microsoft Office Word. В рамках этих приложений документ может быть сохранен в формате ASCII, но в этом случае при наборе текста невозможно будет использование некоторых функций.

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

  • Microsoft Excel;
  • Microsoft FrontPage;
  • Microsoft InfoPath;
  • Microsoft OneNote;
  • Microsoft Outlook;
  • Microsoft PowerPoint;
  • Microsoft Project.

При этом стоит учитывать, что набирая код ASCII в этих приложениях необходимо удерживать нажатой клавиатурную клавишу ALT.

Конечно, все необходимые коды требует более длительного и обстоятельного изучения, но это выходит за пределы нашей сегодняшней статьи. Надеюсь, что она оказалась для Вас действительно полезной.

До новых встреч!

Добавить комментарий

Закрыть меню