Главная страница
Навигация по странице:

  • ИНФОРМАЦИИ И КОДИРОВАНИЯ УЧЕБНОЕ ПОСОБИЕ

  • Соде ржание ВВЕДЕНИЕ ................................................................................................... 5

  • 2. КОДИРОВАНИЕ ИНФОРМАЦИИ. .................................................. 31

  • СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ. ................................ 140 5 Введение

  • 1. Элементы теории информации. 1.1. Понятия информации, сообщения и сигнала.

  • Рис. 1.1. Простейшие манипулированные сигналы.

  • 1.2. Измерение информации.

  • Информатика. Спиридонов А.И. Основы теории информации и кодирования. Основы теории информации и кодирования


    Скачать 1.58 Mb.
    НазваниеОсновы теории информации и кодирования
    АнкорИнформатика
    Дата30.05.2020
    Размер1.58 Mb.
    Формат файлаpdf
    Имя файлаСпиридонов А.И. Основы теории информации и кодирования.pdf
    ТипУчебное пособие
    #126691
    страница1 из 9

    Подборка по базе: Дополнительные главы теории вероятностей и математической статис, Уход за тяжелыми больными. Основы реанимационно...docx, 74 Основы ГМУ.doc, Качество информации как движущий фактор развития экономики.docx, Колядина Н.М. и др - Основы органической химии лекарственных вещ, Молекулярно-генетические основы наследственности.docx, реферат по дисциплине Основы финансового менеджмента.docx, Яковлев А И Основы уголовного права.rtf, реферат основы нейрофизиолигии.docx, Предмет и метод экономической теории.docx
      1   2   3   4   5   6   7   8   9

    Министерство образования и науки
    Российской Федерации
    ПСКОВСКИЙ ГОСУДАРСТВЕННЫЙ
    ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ
    А.И. Спиридонов
    ОСНОВЫ ТЕОРИИ
    ИНФОРМАЦИИ
    И КОДИРОВАНИЯ
    УЧЕБНОЕ ПОСОБИЕ
    Санкт-Петербург
    2004

    2
    УДК 681.3.053
    Р е к о м е н д о в а н о к и з д а н и ю
    н а у ч н о - м е т о д и ч е с к и м с о в е т о м
    П с к о в с к о г о г о с у д а р с т в е н н о г о п о л и т е х н и ч е с к о г о и н с т и т у т а
    Рецензенты:
    -
    Ильин С.Н., зам. генерального директора ОАО «СКБ ВТ»
    -
    Григорьев О.Н., доцент каф. Электроэнергетики ППИ
    Учебное пособие «Основы теории информации и коди- рования» по дисциплине «Теория кодирования» (ЕН.Р.02) предназначено для студентов Псковского государственного политехнического института специальности 230101 «Элек- тронные вычислительные машины, комплексы, системы и се- ти» очной, очно-заочной и очной с сокращенным сроком реа- лизации форм обучения.
    В пособии изложены основные положения теории ин- формации и кодирования, принципы построения цифровых, эффективных и корректирующих кодов, способы реализации кодеров и декодеров.
    Учебное пособие может использоваться студентами род- ственных специальностей и специализаций.
    Спиридонов А.И. «Основы теории информации и коди- рования». Учебное пособие.
    – СПб/Псков, Изд. СПбГПУ,
    2004 – 140 с.
    © Псковский государственный политехниче- ский институт, 2004.
    © СПбГПУ, 2004.
    © Спиридонов А.И., 2004.

    3
    Соде ржание
    ВВЕДЕНИЕ ................................................................................................... 5
    1. ЭЛЕМЕНТЫ ТЕОРИИ ИНФОРМАЦИИ. .......................................... 7
    1.1.
    П
    ОНЯТИЯ ИНФОРМАЦИИ
    ,
    СООБЩЕНИЯ И СИГНАЛА
    . ............................ 7
    1.1.1. Понятие информации. ................................................................. 7
    1.1.2. Понятие сообщения. .................................................................... 8
    1.1.3. Понятие сигнала. ....................................................................... 10
    1.2.
    И
    ЗМЕРЕНИЕ ИНФОРМАЦИИ
    . ................................................................ 12
    1.2.1. Структурные меры информации. ............................................ 13
    1.2.2. Статистическая мера информации. ....................................... 17
    1.3.
    К
    ВАНТОВАНИЕ СИГНАЛОВ
    . ................................................................. 23
    1.3.1. Дискретизация сигналов. .......................................................... 25
    1.3.2. Квантование по уровню. ........................................................... 28
    2. КОДИРОВАНИЕ ИНФОРМАЦИИ. .................................................. 31
    2.1.
    Ц
    ИФРОВОЕ КОДИРОВАНИЕ ИНФОРМАЦИИ
    . ......................................... 31
    2.1.1. Позиционные системы счисления. ........................................... 32
    2.1.2. Смешанные системы счисления. .............................................. 34
    2.1.3. Перевод числа из одной системы счисления в другую. ........... 36
    2.1.4. Коды, не базирующиеся на системах счисления. .................... 39
    2.2.
    Э
    ФФЕКТИВНОЕ КОДИРОВАНИЕ
    . .......................................................... 41
    2.2.1. Избыточность сообщений........................................................ 41
    2.2.2. Теоретические основы эффективного кодирования. ............. 43
    2.2.3. Построение эффективного кода по методам Шеннона-Фано и
    Хаффмена. ............................................................................................ 45
    2.2.4. Кодирование укрупненными блоками. ...................................... 50
    2.3.
    Т
    ЕОРЕТИЧЕСКИЕ ОСНОВЫ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ
    . . 52
    2.3.1. Теоремы Шеннона о помехоустойчивом кодировании. .......... 53
    2.3.2. Классификация помехоустойчивых кодов. .............................. 54
    2.3.3. Общие принципы использования избыточности при
    построении корректирующих кодов. ................................................. 55
    2.3.4. Избыточность корректирующих кодов. ................................. 60
    2.4.
    К
    ОДЫ
    ,
    ОБНАРУЖИВАЮЩИЕ ОШИБКИ
    . ................................................ 61 2.5.
    Л
    ИНЕЙНЫЕ КОДЫ
    ,
    ОБНАРУЖИВАЮЩИЕ И ИСПРАВЛЯЮЩИЕ ОШИБКИ
    .65
    2.5.1. Построение двоичного линейного кода. .................................. 68
    2.5.2. Кодирование. .............................................................................. 74
    2.5.3. Синдромный метод декодирования. ........................................ 76
    2.5.4. Кодирующее и декодирующее устройства. ............................ 79
    2.5.5 Коды Хэмминга. .......................................................................... 84
    2.5.6. Матричное представление линейных кодов. ........................... 86

    4
    2.5.7. Мажоритарное декодирование. .............................................. 95
    2.6.
    Ц
    ИКЛИЧЕСКИЕ КОДЫ
    . ......................................................................... 98
    2.6.1. Выбор образующего многочлена. ........................................... 101
    2.6.2. Формирование разрешенных кодовых комбинаций. ............. 104
    2.6.3. Декодирование циклических кодов. ........................................ 107
    2.6.4. Циклические коды с
    d
    3

    . .................................................... 110
    2.6.5. Кодирующее и декодирующее устройства. .......................... 112
    2.6.6. Мажоритарное декодирование. ............................................ 125
    2.6.7. Матричное представление циклических кодов. .................... 129
    2.7.
    К
    РАТКИЕ СВЕДЕНИЯ О ДРУГИХ КОДАХ
    . ............................................ 131 2.8.
    П
    ОНЯТИЕ ОБ АДАПТИВНОМ КОДИРОВАНИИ
    . .................................... 135
    СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ. ................................ 140

    5
    Введение
    Во второй половине 20 в. человечество вступило в но- вый этап своего развития, заключающийся в переходе от ин- дустриального общества к информационному. Процесс, обес- печивающий этот переход, получил название информатиза- ции и состоит в реализации комплекса мер, направленных на обеспечение полного и своевременного использования досто- верных знаний во всех общественно значимых видах челове- ческой деятельности.
    Теоретическим фундаментом процесса информатизации является информатика. Впервые термин «информатика» (in- formatics) появился во Франции в 60-х годах после того, как
    Французская академия приняла его вместо понятия «обработ- ка информации». После этого он стал широко использоваться в Европе и только в США и в Англии для обозначения рас- сматриваемой области деятельности используется термин
    «computer science». Буквальный перевод «computer science» – вычислительная наука, но это неверно по смыслу. По мнению академика А.А. Дородницына «computer science» – наука о преобразовании информации, в самом своем существе бази- рующаяся на применении вычислительной техники (ВТ).
    Появление информатики как самостоятельной научной дисциплины обусловлено возникновением и распространени- ем новой технологии сбора, передачи, обработки и преобра- зования информации, основанной на широком использовании средств ВТ и фиксации данных на машинных носителях. Но информатика – это не просто вычислительная технология, а вычислительная технология, органически встроенная в среду применения и преобразующая ее в соответствии с возможно- стями ЭВМ и потребностями самой среды применения. Воз- действие вычислительной технологии на среду применения – главный отличительный элемент информатики как особой дисциплины.
    Информатика, являясь новой научной областью, при решении своих задач опирается на такие традиционные

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

    7
    1. Элементы теории информации.
    1.1. Понятия информации, сообщения и сигнала.
    1.1.1. Понятие информации.
    Информация наряду с материей и энергией является первичным понятием мира и поэтому в строгом смысле не может быть определена. Сам термин «информация» происхо- дит от лат. «informatio» – разъяснение, осведомление.
    Имеется множество определений понятия информации.
    В наиболее общем понимании информация есть отражение реального мира; это сведения, которые один реальный объект содержит о другом реальном объекте. В узком практическом понимании информация есть все сведения, представляющие интерес, подлежащие регистрации и обработке.
    Сама по себе информация может быть отнесена к кате- гории абстрактных понятий типа математических, но ряд ее особенностей приближает ее к материальным объектам. Так, информацию можно получить, записать, удалить, передать; информация не может возникнуть из ничего. Однако при рас- пространении информации проявляется такое ее свойство, ко- торое не присуще материальным объектам: при передаче ин- формации из одной системы в другую количество информа- ции в передающей системе не уменьшится, хотя в принима- ющей системе оно обычно увеличивается.
    Понятие информации связано не с реальными вещами, а их моделями, отражающими сущность реальных вещей в той степени, в какой это необходимо для практических целей. В общем виде информация о различных природных явлениях и процессах может быть представлена в виде тех или иных по- лей. Математически такие поля описываются с помощью функций типа:


    N
    ,
    T
    f x

    ,
    (1.1) где x
    – физическая величина, характеризующая поле в мо- мент времени
    T
    в точке пространства
    N

    8
    Если все величины, входящие в приведенное соотноше- ние, могут принимать непрерывный ряд значений, измеряе- мых вещественными числами, то такую информацию назы- вают непрерывной. Если же установить минимальные шаги измерения всех величин, характеризующих поле x
    , то полу- чим так называемое дискретное представление информации.
    Практически точность любых измерений, как и челове- ческое восприятие, всегда ограничена, поэтому фактически, даже имея дело с непрерывной информацией, человек вос- принимает ее в дискретном виде. Кроме того, любая непре- рывная информация может быть аппроксимирована дискрет- ной информацией с любой степенью точности, поэтому дис- кретную информацию можно считать универсальной формой ее представления.
    1.1.2. Понятие сообщения.
    Информация, зафиксированная в определенной форме, называется сообщением. Как и информация, сообщения бы- вают непрерывными и дискретными.
    Непрерывное сообщение – это некоторая физическая, чаще всего электрическая величина, принимающая любые значения в заданном интервале и изменяющаяся в произволь- ные моменты времени.
    Дискретное сообщение представляет собой последова- тельность отдельных элементов, разграниченных во времени и выбранных из некоторого набора. Физическая природа этих элементов безразлична; важно лишь, чтобы набор элементов был конечным и фиксированным.
    Набор, из которого выбирают элементы, слагающие дискретное сообщение, называют алфавитом, а сами элемен- ты – буквами, знаками или символами. Число различных букв в алфавите называют его объемом.
    Дискретные сообщения часто разбивают на отдельные блоки конечной длины. Такие блоки, по аналогии с обычным языком, называют словами.

    9
    Длина блоков часто стандартизируется. В этих случаях представление информации называют однородным. Одно- родное представление информации имеет место в ЭВМ, где информация представляется в виде блоков равной длины, определяемой разрядностью ячеек памяти машины.
    Процесс описания смыслового содержания информации с помощью символов (букв) называется кодирование. Обрат- ный процесс, т.е. выявление смыслового содержания инфор- мации в принятых символах, называют декодированием.
    При обработке информации часто возникает необходи- мость представлять буквы одного алфавита с большим объе- мом в другом алфавите с меньшим объемом. Операция пере- хода от первичного алфавита к вторичному также называется кодированием.
    Поскольку объем вторичного алфавита меньше объема первичного, то каждому знаку первичного алфавита соответ- ствует некоторая последовательность знаков вторичного ал- фавита, обычно называемая кодовой комбинацией. Число символов в кодовой комбинации называется ее значностью, а число ненулевых символов – весом. Операцию сопоставления кодовой комбинации соответствующего ей знака первичного алфавита также называют декодированием.
    Для того чтобы потребитель информации мог распо- знать сообщение, т.е. отождествить символы с какими-либо объектами или процессами реального мира, он должен обла- дать определенными сведениями (алфавит, правило построе- ния кода и т.п.).
    Сведения, которыми располагает потребитель информа- ции до ее получения и на знание которых рассчитывает от- правитель, называют априорными (доопытными).
    Сведения, которыми располагает потребитель после ин- формационного обмена, называют апостериорными (после- опытными).

    10
    1.1.3. Понятие сигнала.
    Сама по себе информация не материальна, но она явля- ется свойством материи и не может существовать без своего материального носителя – средства переноса информации в пространстве и во времени. В качестве носителей информа- ции могут выступать самые разнообразные процессы и объек- ты, такие как электромагнитные волны, давление, механиче- ское перемещение каких-либо объектов, бумага и т.д.
    Все возможные носители сообщений, параметры кото- рых содержат информацию, называют сигналами.
    Формируют сигналы путем изменения одного или не- скольких параметров носителя по закону, отображающему сообщение. Параметры сигнала, используемые для передачи сообщения, называют информационными. Правило, по ко- торому производится изменение информационного параметра носителя при передаче сообщения, называют правилом ко-
    дирования или просто кодом.
    Для передачи информации требуется, чтобы сигналы кроме информационных параметров имели и параметры се-
    лекции (отбора), позволяющие выделить полезный сигнал из совокупности других сигналов и помех.
    Управление информационным параметром носителя в соответствии с передаваемым сообщением называется моду-
    ляцией. В зависимости от типа и числа параметров носителя может быть большое число различных методов модуляции.
    Например, если в качестве переносчика сообщений использу- ется гармоническое колебание
     







    t cos a
    t x
    , где a – амплитуда,

    – угловая частота,

    – начальная фаза, то может быть три метода модуляции: амплитудная (АМ), ча- стотная (ЧМ) и фазовая (ФМ).
    Применяют и комбинированные методы модуляции, ко- гда в соответствии с передаваемым сообщением одновремен- но изменяется несколько параметров носителя. Примером

    11 может служить амплитудно-квадратурная модуляция, пред- ставляющая собой сочетание фазовой и амплитудной модуля- ций (применяется в модемах). Во всех случаях комбиниро- ванной модуляции один из параметров носителя не должен изменяться, чтобы играть роль параметра селекции.
    Если при модуляции информационный параметр изме- няется скачкообразно и имеет конечное число значений, то модуляцию называют манипуляцией. При гармоническом носителе манипулированные сигналы обозначают:
    АМн
    ,
    ЧМн
    ,
    ФМн
    . Примеры манипулированных сигналов приве- дены на рис. 1.1.
    Информационный сигнал t
    t t
    t
    1 0
    1 1
    0 0
    1 0
    0 0
    0 0
    1

    0

    - код активная пауза
    АМн
    ЧМн
    ФМн
    1

    1

    0

    1

    0

    0

    1

    0

    1

    1

    0

    0

    1

    0

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

    12 прямоугольной формы. Так представляется информационный сигнал, отображающий сообщение, поступающее, например, с выхода ЭВМ в двоичном коде.
    Амплитудная модуляция связана с изменением ампли- туды высокочастотного колебания. При
    АМн с пассивной паузой сигнал передается только при передаче "
    1
    "
    (может быть и наоборот), а при
    АМн с активной паузой сигнал пере- дается всегда, но отличается амплитудами.
    Частотная манипуляция состоит в том, что символы "
    0
    "
    и "
    1
    "
    передаются синусоидами, имеющими различные часто- ты. На рис. 1.1 разность
    0 1






    сделана слишком боль- шой для наглядности, в реальных системах


    значительно меньше.
    При фазовой манипуляции фаза синусоидального сигна- ла изменяется на

    180
    при изменении информационного сиг- нала от "
    0
    "
    к "
    1
    "
    и от "
    1
    "
    к "
    0
    "
    1.2. Измерение информации.
    Ценность теоретико-информационных представлений заключается в том, что благодаря их общности и абстрактно- сти существенно разнородные физические и технические ха- рактеристики можно выразить через некоторые универсаль- ные понятия теории информации и сопоставить их не только качественно, но и количественно.
    Существуют три направления в теории информации, связанные с ее количественной оценкой – структурное, стати- стическое и прагматическое.
    Структурная теория рассматривает дискретное строение массивов информации и ее измерение либо простым подсчетом информационных элементов, либо комбинаторным методом.
    Статистическая теория оперирует понятием энтропии, характеризующей неопределенность сообщений и учитыва- ющей вероятность их появления.

    13
    Прагматическая теория изучает вопросы о практическом использовании информации, о ее ценности для достижения поставленной цели.
    В инженерной практике наибольшее применение нахо- дят первые две теории, поэтому ограничимся только их рас- смотрением.
    Независимо от направления теории информации при ко- личественном ее определении должны выполняться следую- щие общие принципы:
    – количественная мера информации не должна зави- сеть от физической природы объекта или процесса;
    – мера должна быть такой, чтобы количество инфор- мации в данной мере было тем больше, чем больше априорная неопределенность ситуации;
    – количественная мера должна удовлетворять принци- пу аддитивности, согласно которому количество ин- формации должно изменяться прямо пропорцио- нально длительности сообщения.
    Рассмотрим меры информации, удовлетворяющие пере- численным требованиям.
    1.2.1. Структурные меры информации.
    Структурные меры информации применяются для оцен- ки возможностей аппаратуры или сообщений вне зависимости от условий их применения.
    В структурной теории различают геометрическую, ком- бинаторную и аддитивную меры информации.
      1   2   3   4   5   6   7   8   9


    написать администратору сайта