Показано с 1 по 3 из 3

Тема: Кодирование информации. Задумки.

  1. #1
    Администратор, Консультант по математике
      За вклад в развитие форума 2006, Лучший знаток физики 2007, Самый активный автор месяца. Август 2007, Лучший консультант 2007, Лучший супермодератор 2007, Народный модератор раздела "Наука и Образование" 2008, Лучший супермодератор 2008, Лучший консультант 2008
    Аватар для Trotil
    Регистрация
    15.12.2005
    Адрес
    град Москва
    Сообщений
    5,890
    Записей в блоге
    26
    Спасибо
    я - 57; мне - 380

    Кодирование информации. Задумки.

    Информация может быть представлена в виде символов. Набор возможных символов в информации определяет язык. В русском языке 33 буквы. Это означает, что символ может принимать 33 значения.
    Особенность цифровой передачи данных - то, что у передаваемого сигнала может быть только два состояния в момент времени - либо есть сигнал (1), либо его нет(0). Единицу сигнала мы назовем битом информации.
    Алфавит мощностью более двух символов закодировать в один момент времени невозможно. Поэтому выходом из этой ситуации стало передавать ее некоторой последовательностью бит. В самом деле:
    1 бит информации: 0, 1 - два значения
    2 бита информации 00, 01, 10, 11 - четыре значения
    3 бита информации - 000, 001, 010, 011, 100, 101, 110, 111 - 8 различных комбинаций.
    и так далее. Каждую такую комбинацию можно поставить в соответствие некоторому символу, что будет однозначно определять этот символ.
    Договорились, что оптимальным будет 8-ми битная группировка данных. Восемь бит равно 1 байту. 1 байт может принимать 256 различных значений. Именно такие "группировки" по 8 бит можно увидеть, открыв любой файл текстовым редактором, хотя, строго говоря, если в файле двоичные данные, это разбиение весьма условно.
    Существует две основные задачи с такими двоичными данными:
    - сжатие данных. Представим себе текстовый файл (содержащий текст, осмысленные слова). Из 256 возможных символов В тексте используется лишь около четверти. Следовательно, кодирование текста таким способом - нерационально и мы можем, используя специальные различные алгоритмы, уменьшить количество бит, необходимых для передачи этой информации. Кроме того, сжатие может происходить за счет поиска повторяющихся фрагментов кода.
    - избыточное кодирование для обнаружения и исправления ошибок при передачи данных. Допустим, файл в процессе передачи данных исказился. Чтобы можно было выявить (и исправлять) такие искажения, используют избыточные кодирование. За счет дополнительных бит к исходному сообщению можно решить такую задачу.
    Отдельной строкой лежит задача шифрования данных. Текст в исходном сообщении преобразовывается, становясь нечитаемым для окружающих. При перехвате шифрованного текста получить исходный практически невозможно без дополнительной информации (например, без знания ключа и алгоритма, по которому был зашифрован этот файл)

    Все три области преобразований текста, ставя перед собой конкретные задачи, по своему интересны.

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

  2. #2
    Группа удаления Аватар для NoX
    Регистрация
    10.10.2005
    Адрес
    Бездна
    Сообщений
    71
    Спасибо
    я - 0; мне - 0
    расскажи про кодирование для обнаружения и исправления ошибок пожалуйста
    Нокс

  3. #3
    Администратор, Консультант по математике
      За вклад в развитие форума 2006, Лучший знаток физики 2007, Самый активный автор месяца. Август 2007, Лучший консультант 2007, Лучший супермодератор 2007, Народный модератор раздела "Наука и Образование" 2008, Лучший супермодератор 2008, Лучший консультант 2008
    Аватар для Trotil
    Регистрация
    15.12.2005
    Адрес
    град Москва
    Сообщений
    5,890
    Записей в блоге
    26
    Спасибо
    я - 57; мне - 380
    При передачи информации некоторые биты информации могут неверно быть переданы получателю. Если наш канал передачи информации не застрахован от ошибок, рано или поздно может случиться это неприятность.
    Пусть вероятность ошибки будет мала - на 1 Mb информации искажается 1 бит), то при передаче, скажем, N=100 Мб вероятность безошибочной передачи данных эта вероятность равна (1-0.00001)^100 и с ростом N эта величина будет довольно быстро уменьшаться. Что мы и наблюдаем, особенно, когда люди передают архивы dual-up-ом - при плохих каналах архивы часто становятся битыми.
    На помощь решения этой проблемы приходит избыточное кодирование.

    Схема:
    ИСТОЧНИК - КОДЕР -(передача данных, с вероятностью искажения) - ДЕКОДЕР - ПРИЕМНИК.
    Для начальной иллюстрации такой пример: пусть каждый бит информации мы будем утраивать: 0->000, 1->111 (каждый бит мы будем передавать 3 раза). Тогда декодирование будет происходить по принципу наибольшего правдоподобия:
    000 - 0
    001 - 0
    010 - 0
    011 - 1
    100 - 0
    101 - 1
    110 - 1
    111 - 1
    Такая функция называется еще мажоритарной или функцией голосования. Подсчитывается, сколько в порции бит единиц, а сколько нулей - и тех, что больше - считаем за правильный ответ, Код, построенный таким образом, Обнаруживает две ошибки и исправляет одну. В самом деле: если в "000" исказился только один бит информации (100, 001, 010), то мажоритарная функция вернет 0 (нулей в таком случае все равно больше). Если произошли два ошибки, 000->101, декодер обнаружит ошибку, но декодирует ее неверно. Поэтому можно говорить о том, что код, построенный таким образом может исправить только одну ошибку.
    Возьмем такое преобразование: 0->0000, 1->1111. Тогда при получении
    0010 - можно говорить, что передавался 0,
    1011 - можно говорить о том, что передавалась 1, а
    1001 - здесь можно сказать, что произошла ошибка, но определить, что именно передавалось, 0000 или 1111 мы не сможем. Таким образом можно говорить о том, что этот код - исправляет одну ошибку, но обнаруживает две.

    Вернемся к коду 0->000, 1->111. Пусть вероятность ошибки в канале будет равна p и передавалось 0->000. Тогда
    Полученная информация Вероятность ошибки
    000 (1-p)^3
    001 p*(1-p)^2
    010 p*(1-p)^2
    011 (1-p)*p^2
    100 p*(1-p)^3
    101 (1-p)*p^2
    110 (1-p)*p^2
    111 p^3
    Нетрудно подсчитать, что увеличении длины кода в 3 раза, вероятность повышается существенно более, чем в 3 раза.

    Анонс:
    Параметры кода:
    длина кода
    число исправляемых ошибок
    число обнаруживаемых ошибок
    число обнаруживаемых ошибок в режиме обнаружения ошибок

    Линейные коды: порождающая и проверочные матрицы, синдромы
    Коды Хемминга
    проверка на четность
    БЧХ-коды (очень кратко, только пример)
    Понятие CRC и хэша.

    К сожалению, многие найденные важные коды основаны на структурах колец многочленов и теории полей Галуа. Кроме того, эти алгебраические понятия и методы являются необходимым рабочим инструментом для конструирования кодеров и декодеров. Так как я стараюсь говорить языком школьника (не всегда, правда, получается ), поэтому естественно про такие коды я рассказывать не буду, но обозначенного выше материала вполне достаточно, чтобы иметь представление об этой области.
    Ленивый дурак - это полбеды; деятельный дурак - это для всех головная боль, но нет ничего хуже, чем дурак с инициативой, да ещё и при должности.

Похожие темы

  1. Высказывания о The Sims в средствах массовой информации и их обсуждение
    от Мавел в разделе The Sims 1: Опросы, голосования, истории
    Ответов: 80
    Последнее сообщение: 23.12.2003, 21:51

Ваши права

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