- •3. Аппаратное обеспечение и архитектура современного пк
- •Сущность и особенности дистанционного обучения
- •Правовые основы применения дистанционных образовательных технологий в рф
- •Системы дистанционного обучения, их классификация
- •Жизненный цикл (жц) информационной системы. Основные процессы жизненного цикла. Вспомогательные процессы. Организационные процессы. Технологии проектирования информационных систем.
- •Техническое задание на проектирование информационной системы. Основные разделы технического задания. Стандарты, описывающие техническое задание. Анализ и разработка требований.
- •Методы аутентификации пользователей информационных систем.
- •Сеть Фейстеля: принцип работы и использование в алгоритмах блочного шифрования
- •Анализ основных технологий разработки электронных технических документов
- •Типовые структуры электронных технических документов
- •Технологии проектирования и реализации мультимедийного продукта.
- •26. Классификации систем компьютерной графики. Кодирование векторной и растровой графической информации. Растровая графика – объекты изображения. Векторная графика – объекты изображения.
- •27. Цветовые модели rgb, cmYk, hsv (hsb), hsl, lab. Представление цветов, кодирование, назначение.
- •28. Структурированная кабельная система: топологии, подсистемы, категории пассивного оборудования.
- •29. Порядок проектирования структурированной кабельной системы.
- •30. Глобальная сеть Интернет. Сетевые протоколы. Модель osi. Система доменных имен, трансляция доменного имени в ip-адрес. Маршрутизация пакетов в сети Интернет.
- •31. Логическое программирование на языке Пролог. Представление знаний о предметной области в виде фактов и правил базы знаний Пролога. Организация повторений.
- •1.1. Метод отката после неудачи.
- •33. Ядро операционной системы. Классификация ядер операционных систем. Достоинства и недостатки различных архитектур ядер операционных систем.
- •34. Файловая система как компонент операционной системы: определение, основные функции и возможности. Примеры реализации файловых систем.
- •35. Информация и энтропия. Измерение количества информации. Свойства информации. Формулы Хартли и Шеннона.
- •37. Коды, обнаруживающие и исправляющие ошибки передачи. Построение систематического кода. Код Хемминга.
- •38. Понятие переменной в языках программирования. Оператор присваивания. Организация ввода и вывода данных в приложении. Организация ветвления и циклов в языках программирования.
- •39. Массив как способ организации данных. Реализация массивов в различных языках программирования. Одномерные и многомерные массивы. Типовые алгоритмы обработки массивов.
- •40. Подпрограммы (методы) в языках программирования. Формальные и фактические параметры. Глобальные и локальные переменные. Рекурсивное выполнение подпрограммы.
37. Коды, обнаруживающие и исправляющие ошибки передачи. Построение систематического кода. Код Хемминга.
В настоящее время основным способом обеспечения достоверности сообщения при их передаче по каналам связи при воздействии помех (шумов) является помехоустойчивое кодирование. Эффективность такого кодирования достигается за счёт введения искусственной избыточности в передаваемое сообщение, что приводит к расширению используемой полосы частот и уменьшению информационной скорости передачи.
Многообразие существующих помехоустойчивых кодов делится на два класса: блочные и непрерывные коды. В блочных кодах передаваемая информационная последовательность разбивается на отдельные блоки с добавлением каждому блоку определённого числа проверочных символов. Кодовые комбинации кодируются и декодируются независимо друг от друга. В непрерывных кодах, передаваемая информационная последовательность не разделяется на блоки, а проверочные символы размещаются в определённом порядке между информационными. Процессы кодирования и декодирования также осуществляются в непрерывном режиме.
Систематический код – это код, в котором разряды распределены на две группы, одна из которых служит, для передачи информации, а вторая – для проверки правильности передачи, причём все разряды занимают строго фиксированные положения.
Рассмотрим построение систематического кода на примере кода Хэмминга.
Коды Хэмминга – это наиболее известные, и, вероятно первые из самоконтролирующихся и самокорректирующихся кодов. Другими словами, это алгоритм, который позволяет закодировать какое-либо информационное сообщение определённым образом и после передачи определить появилась ли какая-то ошибка в этом сообщении (к примеру из-за помех) и, при возможности восстановить это сообщение.
Для того, чтобы понять работу данного алгоритма, рассмотрим пример:
Допустим есть сообщение «habr», которое необходимо передать без ошибок. Для этого нужно наше сообщение закодировать при помощи кода Хэмминга. Нам необходимо представить его в бинарном виде.
На этом этапе стоит определиться с так называемой, длиной информационного слова, то есть длиной строки из нулей и единиц, которые мы будем кодировать. Допустим, у нас длина слова будет равна 16 бит. Таким образом, нам необходимо разделить наше исходное сообщение («habr») y блоки по 16 бит, которые мы будем потом кодировать отдельно друг от друга. Так как один символ занимает в памяти 8 бит, то в одно кодируемое слово помещается ровно два ASCII символа. Итак, мы получили две бинарные строки по 16 бит:
После этого процесс кодирования распараллеливается, и две части сообщения («ha» и «br») кодируются независимо друг от друга. Рассмотрим как это делается на примере первой части.
Прежде всего необходимо вставить контрольные биты. Они вставляются в строго определённых местах – это позиции с номерами, равными степеням двойки. В нашем случае (при длине информационного слова в 16 бит) это будут позиции 1, 2, 4, 8, 16. Соответственно получилось 5 контрольных бит.
Было:
INCLUDEPICTURE "http://habrastorage.org/storage2/7e3/8f2/0fe/7e38f20fe4ac07f834f5a68ec775a829.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/7e3/8f2/0fe/7e38f20fe4ac07f834f5a68ec775a829.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/7e3/8f2/0fe/7e38f20fe4ac07f834f5a68ec775a829.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/7e3/8f2/0fe/7e38f20fe4ac07f834f5a68ec775a829.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/7e3/8f2/0fe/7e38f20fe4ac07f834f5a68ec775a829.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/7e3/8f2/0fe/7e38f20fe4ac07f834f5a68ec775a829.png" \* MERGEFORMATINET
Стало:
INCLUDEPICTURE "http://habrastorage.org/storage2/14f/13a/b50/14f13ab5014ce60d2a6a04275d144331.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/14f/13a/b50/14f13ab5014ce60d2a6a04275d144331.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/14f/13a/b50/14f13ab5014ce60d2a6a04275d144331.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/14f/13a/b50/14f13ab5014ce60d2a6a04275d144331.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/14f/13a/b50/14f13ab5014ce60d2a6a04275d144331.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/14f/13a/b50/14f13ab5014ce60d2a6a04275d144331.png" \* MERGEFORMATINET
При этом длина сообщения увеличилась на 5 бит.
Теперь необходимо вычислить значение каждого контрольного бита. Значение каждого контрольного бита зависит от значений информационных бит, но не от всех, а только от тех, который этот контрольный бит контролирует. Для того, чтобы понять, за какие биты отвечает каждых контрольный бит необходимо понять очень простую закономерность: контрольный бит с номером N контролирует все последующие N бит через каждые N бит, начиная с позиции N. Не очень понятно, но по картинке, думаю, станет яснее:
INCLUDEPICTURE "http://habrastorage.org/storage2/5bb/3f1/983/5bb3f198377397fa041e5bb390eec466.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/5bb/3f1/983/5bb3f198377397fa041e5bb390eec466.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/5bb/3f1/983/5bb3f198377397fa041e5bb390eec466.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/5bb/3f1/983/5bb3f198377397fa041e5bb390eec466.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/5bb/3f1/983/5bb3f198377397fa041e5bb390eec466.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/5bb/3f1/983/5bb3f198377397fa041e5bb390eec466.png" \* MERGEFORMATINET
Здесь знаком «X» обозначены те биты, которые контролирует контрольный бит, номер которого справа. То есть, к примеру, бит номер 12 контролируется битами с номерами 4 и 8. Ясно, что чтобы узнать какими битами контролируется бит с номером N надо просто разложить N по степеням двойки.
Но как же вычислить значение каждого контрольного бита? Делается это очень просто: берём каждый контрольный бит и смотрим сколько среди контролируемых им битов единиц, получаем некоторое целое число и, если оно чётное, то ставим ноль, в противном случае ставим единицу.
Высчитав контрольные биты для нашего информационного слова получаем следующее:
INCLUDEPICTURE "http://habrastorage.org/storage2/719/e5c/30a/719e5c30a55f74f58db64960cbe01191.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/719/e5c/30a/719e5c30a55f74f58db64960cbe01191.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/719/e5c/30a/719e5c30a55f74f58db64960cbe01191.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/719/e5c/30a/719e5c30a55f74f58db64960cbe01191.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/719/e5c/30a/719e5c30a55f74f58db64960cbe01191.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/719/e5c/30a/719e5c30a55f74f58db64960cbe01191.png" \* MERGEFORMATINET
и для второй части:
INCLUDEPICTURE "http://habrastorage.org/storage2/f4c/b23/f09/f4cb23f09724cc292f3de4b4730d9650.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/f4c/b23/f09/f4cb23f09724cc292f3de4b4730d9650.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/f4c/b23/f09/f4cb23f09724cc292f3de4b4730d9650.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/f4c/b23/f09/f4cb23f09724cc292f3de4b4730d9650.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/f4c/b23/f09/f4cb23f09724cc292f3de4b4730d9650.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/f4c/b23/f09/f4cb23f09724cc292f3de4b4730d9650.png" \* MERGEFORMATINET
Вот и всё! Первая часть алгоритма завершена.
Теперь, допустим, мы получили закодированное первой частью алгоритма сообщение, но оно пришло к нас с ошибкой. К примеру мы получили такое (11-ый бит передался неправильно):
INCLUDEPICTURE "http://habrastorage.org/storage2/e14/9f0/22e/e149f022e390deae045650c6e17c03ba.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/e14/9f0/22e/e149f022e390deae045650c6e17c03ba.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/e14/9f0/22e/e149f022e390deae045650c6e17c03ba.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/e14/9f0/22e/e149f022e390deae045650c6e17c03ba.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/e14/9f0/22e/e149f022e390deae045650c6e17c03ba.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/e14/9f0/22e/e149f022e390deae045650c6e17c03ba.png" \* MERGEFORMATINET
Вся вторая часть алгоритма заключается в том, что необходимо заново вычислить все контрольные биты (так же как и в первой части) и сравнить их с контрольными битами, которые мы получили. Так, посчитав контрольные биты с неправильным 11-ым битом мы получим такую картину:
INCLUDEPICTURE "http://habrastorage.org/storage2/989/a6d/122/989a6d1229152233eb9c11b1a77d1e74.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/989/a6d/122/989a6d1229152233eb9c11b1a77d1e74.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/989/a6d/122/989a6d1229152233eb9c11b1a77d1e74.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/989/a6d/122/989a6d1229152233eb9c11b1a77d1e74.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/989/a6d/122/989a6d1229152233eb9c11b1a77d1e74.png" \* MERGEFORMATINET INCLUDEPICTURE "http://habrastorage.org/storage2/989/a6d/122/989a6d1229152233eb9c11b1a77d1e74.png" \* MERGEFORMATINET
Как мы видим, контрольные биты под номерами: 1, 2, 8 не совпадают с такими же контрольными битами, которые мы получили. Теперь просто сложив номера позиций неправильных контрольных бит (1 + 2 + 8 = 11) мы получаем позицию ошибочного бита. Теперь просто инвертировав его и отбросив контрольные биты, мы получим исходное сообщение в первозданном виде! Абсолютно аналогично поступаем со второй частью сообщения.