- •Лекция 1 Основные понятия Об информационно-библиотечной культуре
- •Информация, сведения, данные, знания
- •Лекция 2 Неформальные и формальные каналы коммуникации
- •Библиотеки, библиография и библиографическое описание
- •Библиотечная и информационная деятельность
- •Тенденции развития основных видов документов
- •Закономерности роста и старения
- •Оценка значимости (влиятельности) ученых и журналов
- •Закон рассеяния статей конкретной тематики по журналам
- •Лекция 3 Предыстория и сущность
- •Процедуры и понятия
- •Координатное индексирование
- •Цитирование, библиографическое сочетание, социтирование
- •Рубрикаторы информационных изданий
- •Лекция 4 Электронные издания
- •Информационные ресурсы, структуры и инфраструктура
- •Информационные продукты и услуги
- •Лекция 5 Основные понятия и проблемы становления информационного общества. Информатизация как процесс перехода к информационному обществу
- •Возникновение, этапы развития и технологические аспекты информатизации
- •Положительные и отрицательные последствия информатизации
- •Программы информатизации
- •Программы информатизации России
- •Электронное правительство
- •Лекция 6 Представления информации Сообщение как материальная форма представления информации
- •Формы сообщений (сигналы, изображения, знаки, языковые сообщения)
- •Основные понятия теории формальных языков
- •Модели источников сообщений. Конечный вероятностный источник сообщений
- •Кодирование сообщений источника и текстов. Равномерное кодирование. Дерево кода
- •Неравномерное кодирование. Средняя длина кодирования
- •Префиксные коды
- •Необходимые и достаточные условия существования префиксного кода с заданными длинами кодовых слов. Неравенство Крафта
- •Методы построения кодов. Код Фано
- •Избыточность кодирования. Нижняя граница средней длины кодирования
- •Оптимальное кодирование, свойства оптимальных кодов, построение оптимальных кодов методом Хафмена
- •Лекция 7 Модель процесса передачи. Двоичный симметричный канал
- •Способы повышения надежности передачи сообщений
- •Принципы обнаружения и исправления ошибок с использованием кодов
- •Расстояние Хеминга и корректирующие возможности кодов
- •Оценки верхних границ корректирующих способностей кодов
- •Особенности векторных пространств над конечным полем gf(2). Линейный групповой код
- •Построение линейного кода по заданной порождающей матрице
- •Декодирование линейного кода по синдрому
- •Описание процесса обработки данных. Понятие алгоритма и его свойства. Способы формальной записи алгоритмов
- •Модель процесса обработки данных. Конечные автоматы
- •Сеть Петри как модель параллельно выполняемых процессов обработки
- •Формальное определение сети Петри
- •Основные задачи анализа процессов обработки, решаемые с использованием сетей Петри
- •Матричный метод анализа сетей Петри
- •Иерархия информационных систем управления Трансакционные системы
- •Системы бизнес-интеллекта
- •Аналитические приложения
- •Сущность erp-систем
- •Управление запасами и производством
- •Управление спецификациями изделий и технологиями производства
- •Планирование операций
- •Управление продажами
- •Управление запасами
- •Управление закупками
- •Управление производственными процессами
- •Учет и управление финансами Сущность финансового и управленческого учета
- •Главная книга
- •Расчеты с дебиторами
- •Расчеты с кредиторами
- •Основные средства
- •Денежные средства
- •Материально-производственные запасы
- •Расчеты с персоналом
- •Налоговый учет
- •Бухгалтерская отчетность
- •Аналитические возможности
- •Управление персоналом
- •Ограниченность erp-систем
- •Сущность систем бизнес-интеллекта
- •Хранилища данных Функциональность
- •Olap-системы Функциональность
- •Средства формирования запросов и визуализации данных Функциональность
- •Основные виды аналитических приложений
- •Системы управления эффективностью бизнеса (bpm-системы) Сущность концепции bpm
- •Функциональность bpm-систем
- •Управление по ключевым показателям Balanced Scorecard и другие методики управления по ключевым показателям
- •Функциональность bsc-систем
- •Корпоративное планирование и бюджетирование Основы корпоративного планирования и бюджетирования
- •Многомерное хранение информации
- •План счетов
- •Календарь планирования
- •Мультивалютность
- •Бизнес-правила
- •Описание финансовой структуры предприятия
- •Описание пользователей
- •Сценарии и версии
- •Управление процессом планирования
- •Формирование и анализ консолидированной финансовой отчетности Сущность консолидированной финансовой отчетности
- •Информационные системы консолидации финансовой отчетности
- •Аналитические направления
- •Сбор и структурирование исходной информации
- •Мультивалютность
- •Бизнес-правила
- •Журналы
- •Организация процесса консолидации
- •Процедуры консолидации
- •Bi-приложения
- •Системы финансового моделирования
- •Системы имитационного моделирования
- •Определения и термины
- •Области применения имитационных моделей
- •Последовательность разработки имитационных моделей
- •Компьютерная реализация имитационной модели
- •Система Arena
- •Экспертные системы
- •Архитектура экспертной системы
- •Классы экспертных систем
- •Технология создания экспертных систем
- •Рекомендации по выбору экспертной системы
- •Системы поддержки принятия решений
- •Определение систем поддержки принятия решений
- •Характеристика различных систем поддержки принятия решений
- •Выделение признаков классификации сппр
- •Особенности Экспертной системы поддержки принятия решений
- •Архитектура эсппр
- •Реализация выбора метода принятия решения в эсппр
- •Характеристика эсппр по выделенным признакам
- •Специализированные аналитические приложения
- •Принципы построения компьютера История и тенденции развития вычислительной техники
- •Основные характеристики и классификация компьютеров
- •Принципы построения компьютера
- •Структурные схемы и взаимодействие устройств компьютера
- •Компьютерные системы
- •Системы счисления
- •Перевод целых чисел
- •Перевод дробных чисел
- •Арифметические основы эвм Представление числовой информации в компьютере
- •Машинные коды
- •Арифметические операции над числами с фиксированной точкой
- •Логические основы эвм Основные сведения из алгебры логики
- •Законы алгебры логики
- •Техническая интерпретация логических функций
- •Кодирование информации в компьютере
- •Кодирование нечисловой информации
- •Кодирование текстовой информации
- •Кодирование графических данных
- •Кодирование звуковой информации
- •Основная память
- •Сверхоперативная память
- •Ассоциативная память
- •Центральный процессор эвм
- •Система команд микропроцессора
- •Взаимодействие элементов при работе микропроцессора
- •Системы визуального отображения информации (видеосистемы)
- •Клавиатура
- •Принтеры
- •Внешние запоминающие устройства (взу)
- •Накопитель на жестком магнитном диске
- •Оптические запоминающие устройства
- •Организация функционирования эвм с магистральной архитектурой
- •Организация работы эвм при выполнении задания пользователя
- •Особенности управления основной памятью эвм
- •Система прерываний эвм
- •Параллельные вычисления
- •Характеристика и особенности лкс
- •Протоколы и технологии локальных сетей
- •Сетевые устройства лкс
- •Структурированная кабельная система и логическая структуризация лкс
- •Виды глобальных сетей
- •Глобальные сети России РосНиирос
- •Магистральная сеть науки и образования rbNet (Russian Backbone Network)
- •Сеть runNet
- •Узел маршрутизации Российского фонда фундаментальных исследований (рффи)
- •Msk-IX (Московский центр взаимодействия компьютерных сетей Internet eXchange)
- •Сервисы Internet
- •Isp (Internet Service Provider)
- •Ipp (Internet Presence Provider)
- •Pcp (Private Content Publisher)
- •Характеристики хостинг-провайдеров
- •Программное обеспечение Интернета
Расстояние Хеминга и корректирующие возможности кодов
Определение.Код обнаруживаетошибок, еслиошибок в кодовом слове переводит его в слово, которое не входит в код.
Код "Тетраэдр" из предыдущего примера обнаруживает одну ошибку (меняется четность), но не обнаруживает две ошибки. Например, слово 101 в результате двух ошибок в первых двух знаках переходит в другое кодовое слово (реализуется третий вариант передачи на рис.7.7). Легко заметить, что данный код обнаруживает 3 ошибки, 5 ошибок и вообще любое нечетное число ошибок, но не обнаруживает любое четное число ошибок. Поэтому, в соответствии с приведенным определением, этот код не обнаруживает 3 или 5 ошибок, а только одну.
В пространстве вводится мера отличия двух точек этого пространства, которая называется расстоянием Хеминга[29],[33],[34].
Определение. Расстоянием, по Хемингу, между вершинамииназывается число разрядов, в которых эти вершины различаются.
В виде математической формулы это можно записывать так:
где через обозначается абсолютная величина числа.
В качестве примера рассмотрим расстояние Хеминга между двумя точками (последовательностями или словами) ипространства. Эти последовательности отличаются в первой, четвертой и пятой позициях, следовательно,.
Вещественную функцию двух переменных на множествепринято называть расстоянием, если она обладает следующими свойствами:
Расстояние Хеминга обладает перечисленными выше свойствами. Два первых свойства очевидным образом следуют из определения расстояния Хеминга (или из приведенной выше формулы для расстояния Хеминга), а третье свойство вытекает из следующей последовательности равенств и неравенств
Возможности обнаруживать и исправлять ошибки с помощью кода C зависят от его характеристики, которая называется кодовым расстоянием [34].
Определение. Кодовым расстояниемкоданазывается минимальное расстояние между различными кодовыми словами (векторами).
С использованием расстояния Хеминга в пространстве можно определить аналоги таких геометрических понятий, как сфера и шар[34]. Эти понятия потребуются в дальнейшем для объяснения принципов обнаружения и исправления ошибок с помощью кодов.
Сферойрадиусас центром в точкеявляется множество
Число точек в сфереопределяется выражением
Шаром радиуса с центром в точкеназывается множество
Число точек в шареопределяется выражением
Замечание. Если имеется некоторое исходное слово, а словополучилось изв результате одной ошибки, произошедшей, например, при передаче словапо каналу, то, т. е. в смысле Хеминга расстояние между ними равно 1.
Аналогичным образом, если при передаче слова произошлоошибок и оно превратилось в словото.
Утверждение. Код обнаруживаетошибок, если для любых кодовых словиили.
Рассмотрим, как происходит декодирование сообщения после его передачи через канал. Если при передаче не произошло ошибок, то будет получено кодовое слово. Естественно считать это кодовое слово результатом декодирования.
Если в результате передачи получено не кодовое слово, то произошла ошибка. В этом случае целесообразно использовать декодирование в ближайшее кодовое слово. Такой подход имеет объяснение. Действительно, пусть полученное слово ближе к кодовому слову, чем к любому другому кодовому слову, т. е.для всех кодовых слов. Если сравнить различные гипотезы о том, какое исходное слово было пе-редано, то гипотеза о передаче словапри условии получения словаявляется наиболее вероятной. Это следует из того, что первая гипотеза (основная) соответствует меньшему числу ошибок при передаче, чем конкурирующие гипотезы.
Утверждение. Код исправляетошибок, если для любых кодовых словиили.
Для доказательства рассмотрим шары радиуса с центрами в кодовых словах. Из неравенства треугольника для расстояния Хеминга следует, что эти шары не пересекаются. Тогда при передаче любого кодового слова и при числе ошибок, не превышающем, полученное слово будет находиться в шаре с центром в передаваемом слове и декодироваться (по методу декодирования в ближайшее кодовое слово) в переданное слово.
Из последних двух утверждений следует, что важнейшей характеристикой кода, определяющей его корректирующие возможности, является его кодовое расстояние.
Рассмотрим, следуя [34], какие задачи требуется решать при создании кодов, с помощью которых можно эффективно обнаруживать и исправлять ошибки, возникающие при передаче сообщений. Одна из важнейших задач теории кодирования состоит в следующем. Требуется построить код, исправляющийошибок и имеющий максимально возможное число точек. В геометрической постановке эта же задача звучит следующим образом: среди вершин единичного-мерного кубатребуется выделить максимальное число таким способом, чтобы расстояние между любыми двумя выделенными вершинами было не меньше, чем. Это максимальное число обозначается обычно через.
Другая, связанная с предыдущей, задача состоит в расположении точек в вершинахтак, чтобы наименьшее из попарных расстояний между ними было возможно большим. Это расстояние обозначается через.
Выражения "построить", "выделить", "расположить" нуждаются в уточнении, так как нам вовсе не безразлично, в каком виде будет задан искомый код. Самый простой способ - перечисление всех кодовых точек - является неэффективным, требует большой памяти. Поэтому нужен такой способ задания кода, который позволяет просто восстановить каждую точку кода по ее номеру. Другими словами, код должен иметь простую реализацию. С некоторыми просто реализуемыми кодами мы познакомимся ниже. С другой стороны, мы хотим иметь возможность просто восстанавливать исходное сообщение на выходе.
Таким образом, "хороший код" должен удовлетворять следующим трем естественным требованиям:
исправлять много ошибок, т. е. иметь большое кодовое расстояние;
иметь несложную реализацию;
обладать простым алгоритмом исправления ошибок на приемном конце.
Следует отметить, что эти требования в значительной степени являются противоречивыми, так как код , исправляющий много ошибок, вовсе не обязан иметь простую реализацию и тем более простой алгоритм декодирования. Поэтому на практике применяются коды, которые обладают в достаточной мере всеми тремя перечисленными выше качествами.
- максимальное число точек кода в, расстояние между любыми двумя кодовыми словами не меньше.
Для количественной оценки свойств кода полезно знать, насколько его параметры отличаются от параметров "идеального" кода. Для этого необходимо иметь хотя бы приближенные значения важнейших параметров "идеального" кода, т. е. значения и. Следует отметить, что функцииине являются единственными параметрами, характеризующими качество кода. Не менее важными являются также такие параметры кода, как вероятность правильного декодирования и вероятность обнаружения ошибки. Имеется также еще ряд других важных критериев, применяющихся для оценки качества кодов.