Кодировка это в информатике: Информатика — Кодирование

Содержание

Информатика — Кодирование

1. Основные понятия

Закодировать текст – значит сопоставить ему другой текст. Кодирование применяется при передаче данных – для того, чтобы зашифровать текст от посторонних, чтобы сделать передачу данных более надежной, потому что канал передачи данных может передавать только ограниченный набор символов (например, - только два символа, 0 и 1) и по другим причинам.

При кодировании заранее определяют алфавит, в котором записаны исходные тексты (исходный алфавит) и алфавит, в котором записаны закодированные тексты (коды), этот алфавит называется кодовым алфавитом. В качестве кодового алфавита часто используют двоичный алфавит, состоящий из двух символов (битов) 0 и 1. Слова в двоичном алфавите иногда называют битовыми последовательностями.

 2. Побуквенное кодирование

Наиболее простой способ кодирования – побуквенный. При побуквенном кодировании каждому символу из исходного алфавита сопоставляется кодовое слово –

слово в кодовом алфавите. Иногда вместо «кодовое слово буквы» говорят просто «код буквы». При побуквенном кодировании текста коды всех символов записываются подряд, без разделителей.

Пример 1. Исходный алфавит – алфавит русских букв, строчные и прописные буквы не различаются. Размер алфавита – 33 символа.

Кодовый алфавит – алфавит десятичных цифр. Размер алфавита  - 10 символов.

Применяется побуквенное кодирование по следующему правилу: буква кодируется ее номером в алфавите: код буквы А – 1; буквы Я – 33 и т.д.

Тогда код слова АББА – это 1221.

Внимание: Последовательность 1221 может означать не только АББА, но и КУ (К – 12-я буква в алфавите, а У – 21-я буква). Про такой код говорят, что он НЕ допускает однозначного декодирования

Пример 2.  Исходный и кодовый алфавиты – те же, что в примере 1. Каждая буква также кодируется своим номером в алфавите, НО номер всегда записывается двумя цифрами: к записи однозначных чисел слева добавляется 0. Например, код А – 01, код Б – 02 и т.д.

В этом случае кодом текста АББА будет 01020201. И расшифровать этот код можно только одним способом. Для расшифровки достаточно разбить кодовый текст 01020201 на двойки:  01 02 02 01 и для каждой двойки определить соответствующую ей букву.

Такой способ кодирования называется равномерным. Равномерное кодирование всегда допускает однозначное декодирование.

 Далее рассматривается только побуквенное кодирование

 3. Неравномерное кодирование

Равномерное кодирование удобно для декодирования. Однако часто применяют и неравномерные коды, т.е. коды с различной длиной кодовых слов. Это полезно, когда в исходном тексте разные буквы встречаются с разной частотой. Тогда часто встречающиеся символы стоит кодировать более короткими словами, а редкие – более длинными. Из примера 1 видно, что (в отличие от равномерных кодов!) не все неравномерные коды допускают однозначное декодирование.

Есть простое условие, при выполнении которого неравномерный код допускает однозначное декодирование.

Код называется префиксным,  если в нем нет ни одного кодового слова, которое было бы началом (по-научному, - префиксом) другого кодового слова.

Код из примера 1 – НЕ префиксный, так как, например, код буквы А (т.е. кодовое слово 1) – префикс кода буквы К (т.е. кодового слова 12, префикс выделен жирным шрифтом).

Код из примера 2 (и любой другой равномерный код) – префиксный: никакое слово не может быть началом слова той же длины.

Пример 3. Пусть исходный алфавит включает 9 символов: А, Л, М, О, П, Р, У, Ы, -.  Кодовый алфавит – двоичный. Кодовые слова:

А: 00
М: 01
-: 100
Л: 101
У: 1100
Ы: 1101
Р: 1110
О: 11110
П: 11111

Кодовые слова выписаны в алфавитном порядке. Видно, что ни одно из них не является началом другого. Это можно проиллюстрировать рисунком

На рисунке изображено бинарное дерево. Его корень расположен слева. Из каждого внутреннего узла выходит два ребра. Верхнее ребро имеет пометку 0, нижнее – пометку 1. Таким образом, каждому узлу соответствует слово в двоичном алфавите. Если слово X является началом (префиксом) слова Y, то узел, соответствующий слову X, находится на пути из корня в узел, соответствующий слову Y. Наши кодовые слова находятся в листьях дерева. Поэтому ни одно из них не является началом другого.

Теорема (условие Фано). Любой префиксный код (а не только равномерный) допускает однозначное декодирование.

Разбор примера (вместо доказательства). Рассмотрим закодированный текст, полученный с помощью кода из примера 3:

0100010010001110110100100111000011100

    Будем его декодировать таким способом. Двигаемся слева направо, пока не обнаружим код какой-то буквы. 0 – не кодовое слово, а 01 – код буквы М.

0100010010001110110100100111000011100

            Значит, исходный текст начинается с буквы М: код никакой другой буквы не начинается с 01! «Отложим» начальные 01 в сторону и продолжим.

                        

                                                                        01 00010010001110110100100111000011100
                                                                         М

Далее таким же образом находим следующее кодовое слово 00 – код буквы А.

            01 00010010001110110100100111000011100
            М  А

Доведите расшифровку текста до конца самостоятельно.  Убедитесь, что он расшифровывается (декодируется) однозначно.

Замечание. В расшифрованном тексте 14 букв. Т.к. в алфавите 9 букв, то при равномерном двоичном кодировании пришлось бы использовать кодовые слова длины 4. Таким образом, при равномерном кодировании закодированный текст имел бы длину 56 символов – в полтора раза больше, чем в нашем примере (у нас 37 символов).

4. Как все это повторять. Задачи на понимание

Знание приведенного выше материала достаточно для решения задачи 5 из демо-варианта и близких к ней (см.

здесь). Повторять (учить) этот материал стоит в том порядке, в котором он изложен. При этом нужно решать простые задачи – до тех пор, пока не будет достигнуто полное понимание. Ниже приведены возможные типы таких задач. Опытные учителя легко придумают (или подберут) конкретные задачи таких типов. Если будут вопросы – пишите.

1) Понятие побуквенного кодирования.

Дан алфавит Ф и кодовые слова для всех слов в алфавите Ф. Закодировать заданный текст в алфавите Ф. Коды могут быть с использованием разных кодовых алфавитов, равномерные и неравномерные.

2) Префиксные неравномерные коды.

2.1) Дан алфавит Ф и двоичный префиксный код для этого алфавита. Построить дерево кода (см. рис.1) и убедиться, что код – префиксный.

2.2) Дан алфавит Ф и двоичный префиксный код для этого алфавита. Декодировать (анализом слева направо) данный текст в кодовом алфавите.

2.3) Дан алфавит Ф и кодовые слова для всех слов в алфавите Ф. Определить, является ли данный код префиксным, или нет. В качестве примеров полезно приводить:

                        - Равномерный код.
                        - Неравномерный префиксный код (полезно нарисовать депево этого кода как на рис.1).
                        - Различные пополнения данного неравномерного префиксного кода с помощью кода еще одной буквы так, чтобы полученный код либо оставался префиксным, либо переставал им быть. При анализе дополнительной буквы полезно использовать дерево исходного кода. Полезно рассмотреть различные варианты «потери префиксности»: (а) новый код – начало одного из старых; (б) один из старых кодов – начало нового.

            2. 4) Решать задачи для самостоятельного решения, например, отсюда

 

 

 

 

1.6. КОДИРОВАНИЕ ИНФОРМАЦИИ РАЗЛИЧНЫХ ВИДОВ

1.6.1. КОДИРОВАНИЕ ЧИСЕЛ.

Используя n бит, можно записывать двоичные коды чисел от 0 до 2n-1, всего 2n чисел.

1) Кодирование положительных чисел: Для записи положительных чисел в байте заданное число слева дополняют нулями до восьми цифр. Эти нули называют незначимыми.

Например: записать в байте число 1310 = 11012
Результат: 00001101

2) Кодирование отрицательных чисел:Наибольшее положительное число, которое можно записать в байт, - это 127, поэтому для записи отрицательных чисел используют числа с 128-го по 255-е. В этом случае, чтобы записать отрицательное число, к нему добавляют 256, и полученное число записывают в ячейку.

1.6.2. КОДИРОВАНИЕ ТЕКСТА.

Соответствие между набором букв и числами называется кодировкой символа. Как правило, код символа хранится в одном байте, поэтому коды символов могут принимать значение от 0 до 255. Такие кодировки называют однобайтными. Они позволяют использовать 256 символов. Таблица кодов символов называется ASCII (American StandardCodeforInformationInterchange- Американский стандартный код для обмена информацией). Таблица ASCII-кодов состоит из двух частей:

Коды от 0 до 127 одинаковы для всех IBM-PC совместимых компьютеров и содержат:

  • коды управляющих символов;
  • коды цифр, арифметических операций, знаков препинания;
  • некоторые специальные символы;
  • коды больших и маленьких латинских букв.

    Вторая часть таблицы (коды от 128 до 255) бывает различной в различных компьютерах. Она содержит:

  • коды букв национального алфавита;
  • коды некоторых математическихсимволов;
  • коды символов псевдографики.

    В настоящее время все большее распространение приобретает двухбайтная кодировка Unicode. В ней коды символов могут принимать значение от 0 до 65535.

    1.6.3. КОДИРОВАНИЕ ЦВЕТОВОЙ ИНФОРМАЦИИ.

    Одним байтом можно закодировать 256 различных цветов. Это достаточно для рисованных изображений типа мультфильмов, но не достаточно для полноцветных изображений живой природы. Если для кодирования цвета использовать 2 байта, можно закодировать уже 65536 цветов. А если 3 байта – 16,5 млн. различных цветов. Такой режим позволяет хранить, обрабатывать и передавать изображения, не уступающие по качеству наблюдаемым в живой природе.

    Из курса физики известно, что любой цвет можно представить в виде комбинации трех основных цветов: красного, зеленого, синего (их называют цветовыми составляющими). Если кодировать цвет точки с помощью 3 байтов, то первый байт выделяется красной составляющей, второй – зеленой, третий – синей. Чем больше значение байта цветовой составляющей, тем ярче этот цвет.

    Белый цвет – у точки есть все цветовые составляющие, и они имеют полную яркость. Поэтому белый цвет кодируется так: 255 255 255. (11111111 11111111 11111111)

    Черный цвет – отсутствие всех прочих цветов: 0 0 0. (00000000 00000000 00000000)

    Серый цвет – промежуточный между черным и белым. В нем есть все цветовые составляющие, но они одинаковы и нейтрализуют друг друга.
    Например: 100 100 100 или 150 150 150. (2-й вариант - ярче).

    Красный цвет – все составляющие, кроме красной, равны 0. Темно-красный: 128 0 0. Ярко-красный: 255 0 0.

    Зеленый цвет – 0 255 0.

    Синий цвет – 0 0 255.

    1.6.4. КОДИРОВАНИЕ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ.

    Рисунок разбивают на точки. Чем больше будет точек, и чем мельче они будут, тем точнее будет передача рисунка. Затем, двигаясь по строкам слева направо начиная с верхнего левого угла, последовательно кодируют цвет каждой точки. Для черно-белой картинки достаточно 1 байта для точки, для цветной – до 3-х байт для одной точки.

  • Кодирование информации.

    Коды. Системы кодирования

    Для обмена информацией с другими людьми человек использует естественные и формальные языки. Представление информации с помощью какого-либо языка часто называют кодированием.

    Кодирование - это процесс представления информации в виде кода.

    Код - система условных знаков (символов), каждому из которых ставится в соответствие определенное значение.

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

    Код состоит из определенного количества знаков, т. е. имеет определенную длину.

    Количество знаков в коде называется длиной кода.

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

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

    Информация может быть представлена в форме числа, текста, графики или звука.

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

    Чаще всего кодированию подвергаются тексты на естественных языках. Существуют 3 основных способа кодирования текста:

    1.      графический - с помощью специальных рисунков или значков;

    2.     числовой - с помощью чисел;

    3.     символьный - с помощью символов того же алфавита, что и исходный текст.

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

    Рассмотрим некоторые способы кодирования.

    1. Кодированием информации с помощью букв русского алфавита. Суть этого способа заключается в том, чтобы каждую букву сообщения заменить ее номером в алфавите.

    2. Флажковая азбука. При помощи этой азбуки осуществляется передача и прием сообщений между судами и кораблями в пределах прямой видимости. Здесь, каждой букве соответствует определенный флаг.

    3. Азбука Морзе.

    Информация кодируется тремя «буквами»:

    ·        длинный сигнал (тире),

    ·        короткий сигнал (точка),

    ·        отсутствие сигнала (пауза) для разделения букв.

    Таким образом, кодирование сводится к использованию набора символов, расположенных в строго определенном порядке.

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

    5. Перевод чисел из одной системы счисления в другую.

    Пусть требуется перевести двоичное число в десятичную систему счисления.

    Чтобы осуществлять перевод из двоичной системы счисления в десятичную, следует для начала пронумеровать разряды исходного числа справа налево, начиная с нуля.

    Запишем число в виде многочлена, состоящего из произведений цифр числа и соответствующей степени числа 2:

    И вычислив по правилам десятичной арифметики, получили число 232.

    Пусть теперь требуется перевести двоичное число в восьмеричную систему счисления. Для этого следует разбить это двоичное число на триады, начиная с младшего бита.

    Если старшая триада не заполнена до конца, как в нашем случае, следует дописать в ее старшие разряды нули. После этого необходимо заменить двоичные триады, начиная с младшей, на числа, равные им в восьмеричной системе. Это числа: 4, 7, 6, 6, 4, 5, 5, 2.

    Таким образом, наше двоичное число запишется в виде:

    Аналогично поступаем при переводе чисел из двоичной системы счисления в шестнадцатеричную, но разбиение двоичного числа производим на тетрады. Для примера будем использовать то же двоичное число, что и при переводе в восьмеричную систему счисления.

    Заменяя двоичные тетрады на их шестнадцатеричные значения, то есть на C, B, D, C, 6, 5, получим искомое шестнадцатеричное число:

    А теперь давайте мы попробуем перевести число 158 из десятичной в двоичную систему счисления. Для этого нужно выполнить последовательное деление нацело числа 158 на основании новой системы счисления, то есть на 2. Получим:

    Далее число 79 делим на 2. Аналогичные действия выполняем до тех пор, пока частное не станет равным единице.

    Затем запишем остатки от деления в обратном порядке, заменив их цифрами новой системы счисления, т.е. получили число 11101000.

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

    Пусть требуется перевести шестнадцатеричное число F1 в двоичное число. Воспользовавшись таблицей соответствия, получим:

    F соответствуют четыре единицы в двоичной системе счисления, а 1 соответствует такая запись 0, 0, 0, 1 в двоичной системе счисления.

    Итак, число F1 в двоичной системе счисления запишется так 11110001.

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

     

    Кодирование информации. Стандарты кодирования текста

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


    Это означает, что при кодировании текста каждому символу присваивается определенное значение в виде нулей и единиц – байта.

    Зачем кодировать информацию?

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

    Стандарты кодирования текста

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



    ASCII

    Самым первым компьютерным стандартом кодирования символов стал ASCII (полное название - American Standart Code for Information Interchange). Для кодирования любого символа в нём использовали всего 7 бит. Как вы помните, что закодировать при помощи 7 бит можно лишь 27 символов или 128 символов. Этого достаточно, чтобы закодировать заглавные и прописные буквы латинского алфавита, арабские цифры, знаки препинания, а так же определенный набор специальных символов, к примеру, знак доллара - «$». Однако, чтобы закодировать символы алфавитов других народов (в том числе и символов русского алфавита) пришлось дополнять код до 8 бит (28=256 символов). При этом, для каждого языка использовалась свой отдельная кодировка.


    UNICODE

    Нужно было спасать положение в плане совместимости таблиц кодировки. Поэтому, со временем были разработаны новые обновлённые стандарты. В настоящее время наиболее популярной является кодировка под названием UNICODE. В ней каждый символ кодируется с помощью 2-х байт, что соответствует 216=62536 разным кодам.



    Стандарты кодирования графических данных

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


    • изображения растровой графики;
    • изображения векторной графики.

    Растровая графика

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

    Для кодирования чёрно-белого изображения каждый пиксель кодируется одним битом. К примеру, чёрный цвет — 0, а белый — 1)

    Наше прошлое изображение можно закодировать так:

    При кодировании нецветных изображений чаще всего применяют палитру из 256 оттенков серого, начиная от белого и заканчивая чёрным. Поэтому для кодирования такой градации достаточно одного байта (28=256).

    В кодирования цветных изображений применяют несколько цветовых схем.


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

    Таким образом, для кодирования модели из трёх цветов в 256 тонов, получается свыше 16,5 миллионов разных цветовых оттенков. То есть для кодирования применяют 3⋅8=24 бита, что соответствует 3 байтам.

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

    Чтобы определить размер изображения нужно умножить количество пикселей в ширину на длину количество пикселей и ещё раз умножить на размер самого пикселя в байтах.

    I=a*b*i

    Где


    • а - количество пикселей в ширину;
    • b - количество пикселей в длину;
    • I – размер одного пикселя в байтах.

    К примеру, цветное изображение размером 800⋅600 пикселей, занимает 60000 байт.


    Векторная графика

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



    Стандарты кодирования звука

    Звуки, которые слышит человек, представляют собой колебания воздуха. Звуковые колебания – это процесс распространения волн.


    Звук имеет две основные характеристики:


    • амплитуда колебаний – определяет громкость звука;
    • частота колебания - определяет тональность звука.

    Звук можно преобразовать в электрический сигнал, с помощью микрофона. Звук кодируется с определенным, заранее заданным интервалом времени. В этом случае измеряется размер электрического сигнала и присваивается бинарная величина. Чем чаще делают данные измерения, тем выше качество звука.


    Компакт-диск объемом 700 Мб, вмещает порядка 80 минут звука CD-качества.

    Стандарты кодирования видео

    Как вы знаете, видеоряд состоит из быстро меняющихся фрагментов. Смена кадров происходит со скоростью в интервале 24-60 кадров в секунду.

    Размер видеоряда в байтах определяется размером кадра (количеством пикселей на экран по высоте и ширине), количеством используемых цветов, а также количеством кадров в секунду. Но наряду с этим может присутствовать ещё и звуковая дорожка.


    Глоссарий по информатике Система счисления

    Задача №5. Кодирование в различных системах счисления, расшифровка сообщений, выбор кода.

    Автор материалов - Лада Борисовна Есакова.

    Кодирование – это перевод информации, представленной символами первичного алфавита, в последовательность кодов.

    Декодирование (операция, обратная кодированию) – перевод кодов в набор символов первичного алфавита.

    Кодирование может быть равномерное и неравномерное. При равномерном кодировании каждый символ исходного алфавита заменяется кодом одинаковой длины. При неравномерном кодировании разные символы исходного алфавита могут заменяться кодами разной длины.

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

    Равномерное кодирование всегда однозначно декодируемо.

    Для неравномерных кодов существует следующее достаточное (но не необходимое) условие однозначного декодирования:

    Сообщение однозначно декодируемо с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова.

    Сообщение однозначно декодируемо с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова.

     

    Кодирование в различных системах счисления

    Пример 1.

    Для кодирования букв О, В, Д, П, А решили использовать двоичное представление

    чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится

    1) 22162

    2) 1020342

    3) 2131453

    4) 34017

    Решение:

    Представим коды указанных букв в дво­ич­ном коде, добавив незначащий нуль для одноразрядных чисел:

    О

    В

    Д

    П

    А

    0

    1

    2

    3

    4

    00

    01

    10

    11

    100

    Закодируем по­сле­до­ва­тель­ность букв: ВО­ДО­ПАД — 010010001110010.

    Разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём каждую тройку в восьмеричное число.

    010 010 001 110 010 — 22162.

    Пра­виль­ный ответ ука­зан под но­ме­ром 1.

    Ответ: 1

    Пример 2.

    Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из сим­во­лов А, Б, В и Г, ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние: А-10, Б-11, В-110, Г-0. Через канал связи пе­ре­даётся со­об­ще­ние: ВАГ­БА­А­ГВ. За­ко­ди­руй­те со­об­ще­ние дан­ным кодом. По­лу­чен­ное дво­ич­ное число пе­ре­ве­ди­те в шест­на­дца­те­рич­ный вид.

                1) D3A6

    2) 62032206

    3) 6A3D

    4) CADBAADC

     

    Решение:

    За­ко­ди­ру­ем по­сле­до­ва­тель­ность букв: ВАГ­БА­А­ГВ — 1101001110100110. Разобьем это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём каждую четверку в шестнадцатеричное число:

     

    1101 0011 1010 01102 = D3A616

     

    Пра­виль­ный ответ ука­зан под но­ме­ром 1.

    Ответ: 1

    Расшифровка сообщений

    Пример 3.

    Для 5 букв ла­тин­ско­го ал­фа­ви­та за­да­ны их дво­ич­ные коды (для не­ко­то­рых букв – из двух бит, для не­ко­то­рых – из трех). Эти коды пред­став­ле­ны в таб­ли­це:

     

    a

    b

    c

    d

    e

    100

    110

    011

    01

    10

    Опре­де­ли­те, какой набор букв за­ко­ди­ро­ван дво­ич­ной стро­кой 1000110110110, если из­вест­но, что все буквы в по­сле­до­ва­тель­но­сти – раз­ные:

    1) cbade

    2) acdeb

    3) acbed

    4) bacde

     

    Решение:

    Мы видим, что усло­вия Фано и об­рат­ное усло­вие Фано не вы­пол­ня­ют­ся, зна­чит код можно рас­ко­ди­ро­вать не­од­но­знач­но.

    Значит, будем перебирать варианты, пока не получим подходящее слово :

    1) 100 011 01 10 110

    Пер­вая буква опре­де­ля­ет­ся од­но­знач­но, её код 100: a.

    Пусть вто­рая буква — с, тогда сле­ду­ю­щая буква — d, потом — e и b.

    Такой ва­ри­ант удо­вле­тво­ряет усло­вию, зна­чит, окон­ча­тель­но по­лу­чи­ли ответ: acdeb.

     

    Ответ: 2

    Пример 4.

    Для пе­ре­да­чи дан­ных по ка­на­лу связи ис­поль­зу­ет­ся 5-би­то­вый код. Со­об­ще­ние со­дер­жит толь­ко буквы А, Б и В, ко­то­рые ко­ди­ру­ют­ся сле­ду­ю­щи­ми ко­до­вы­ми сло­ва­ми: А — 11010, Б — 10111, В — 01101.

    При пе­ре­да­че воз­мож­ны по­ме­хи. Од­на­ко не­ко­то­рые ошиб­ки можно по­пы­тать­ся ис­пра­вить. Любые два из этих трёх ко­до­вых слов от­ли­ча­ют­ся друг от друга не менее чем в трёх по­зи­ци­ях. По­это­му если при пе­ре­да­че слова про­изо­шла ошиб­ка не более чем в одной по­зи­ции, то можно сде­лать обос­но­ван­ное пред­по­ло­же­ние о том, какая буква пе­ре­да­ва­лась. (Го­во­рят, что «код ис­прав­ля­ет одну ошиб­ку».) На­при­мер, если по­лу­че­но ко­до­вое слово 10110, счи­та­ет­ся, что пе­ре­да­ва­лась буква Б. (От­ли­чие от ко­до­во­го слова для Б толь­ко в одной по­зи­ции, для осталь­ных ко­до­вых слов от­ли­чий боль­ше.) Если при­ня­тое ко­до­вое слово от­ли­ча­ет­ся от ко­до­вых слов для букв А, Б, В более чем в одной по­зи­ции, то счи­та­ет­ся, что про­изо­шла ошиб­ка (она обо­зна­ча­ет­ся 'х').

     

    По­лу­че­но со­об­ще­ние 11000 11101 10001 11111. Де­ко­ди­руй­те это со­об­ще­ние — вы­бе­ри­те пра­виль­ный ва­ри­ант.

     

    1) АххБ

    2) АВхБ

    3) хххх

    4) АВББ

     

    Решение:

    Де­ко­ди­ру­ем каж­дое слово со­об­ще­ния. Пер­вое слово: 11000 от­ли­ча­ет­ся от буквы А толь­ко одной по­зи­ци­ей. Вто­рое слово: 11101 от­ли­ча­ет­ся от буквы В толь­ко одной по­зи­ци­ей. Тре­тье слово: 10001 от­ли­ча­ет­ся от любой буквы более чем одной по­зи­ци­ей. Четвёртое слово: 11111 от­ли­ча­ет­ся от буквы Б толь­ко одной по­зи­ци­ей.

    Таким об­ра­зом, ответ: АВхБ.

    Ответ: 2

    Однозначное кодирование

    Пример 5.

    Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из букв А, Б, В, Г, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный по длине код: A=1, Б=01, В=001. Как нужно за­ко­ди­ро­вать букву Г, чтобы длина кода была ми­ни­маль­ной и до­пус­ка­лось од­но­знач­ное раз­би­е­ние ко­ди­ро­ван­но­го со­об­ще­ния на буквы?

    1) 0001

    2) 000

    3) 11

    4) 101

     

    Решение:

    Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:

     

    Видим, что ближайший от корня дерева свободный лист (т.е. код с минимальной длиной) имеет код 000.

    Ответ: 2

    Пример 6.

    Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв У, Ч, Е, Н, И и К, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный пре­фикс­ный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 011, К — 11. Можно ли со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-преж­не­му остал­ся пре­фикс­ным? Коды осталь­ных букв ме­нять­ся не долж­ны.

    Вы­бе­ри­те пра­виль­ный ва­ри­ант от­ве­та.

    При­ме­ча­ние. Пре­фикс­ный код — это код, в ко­то­ром ни одно ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го; такие коды поз­во­ля­ют од­но­знач­но де­ко­ди­ро­вать по­лу­чен­ную дво­ич­ную по­сле­до­ва­тель­ность.

    1) ко­до­вое слово для буквы Е можно со­кра­тить до 01

    2) ко­до­вое слово для буквы К можно со­кра­тить до 1

    3) ко­до­вое слово для буквы Н можно со­кра­тить до 10

    4) это не­воз­мож­но

     

    Решение:

    Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:


     

    Легко заметить, что если букву Н перенести в вершину 10, она останется листом. Т.е. ко­до­вое слово для буквы Н можно со­кра­тить до 10.

    Пра­виль­ный ответ ука­зан под но­ме­ром 3.

    Ответ: 3

    Ты нашел то, что искал? Поделись с друзьями!

    1.4. Кодирование информации. Основы информатики: Учебник для вузов

    1.4. Кодирование информации

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

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

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

    Для автоматизации работы ЭВМ с информацией, относящейся к различным типам, очень важно унифицировать их форму представления – для этого обычно используется прием кодирования.

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

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

    Символ (или комбинация символов) исходного алфавита, которому соответствует кодовая комбинация, называется исходным символом.

    Совокупность кодовых комбинаций называется кодом.

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

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

    В вычислительной технике также существует своя система кодирования – она называется двоичным кодированием и основана на представлении данных последовательностью всего двух знаков: 0 и 1 (используется двоичная система счисления). Эти знаки называются двоичными цифрами, или битами (binary digital).

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

    N=2m,

    где N – количество независимо кодируемых значений,

    а m – разрядность двоичного кодирования, принятая в данной системе.

    Например, какое количество значений (N) можно закодировать 10-ю разрядами (m)?

    Для этого возводим 2 в 10 степень (m) и получаем N=1024, т. е. в двоичной системе кодирования 10-ю разрядами можно закодировать 1024 независимо кодируемых значения.

    Кодирование текстовой информации

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

    Кодирование графической информации

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

    Для кодирования цветных графических изображений применяется принцип декомпозиции (разложения) произвольного цвета на основные составляющие. При этом могут использоваться различные методы кодирования цветной графической информации. Например, на практике считается, что любой цвет, видимый человеческим глазом, можно получить путем механического смешивания основных цветов. В качестве таких составляющих используют три основных цвета: красный (Red, R), зеленый (Green, G) и синий (Blue, B). Такая система кодирования называется системой RGB.

    На кодирование цвета одной точки цветного изображения надо затратить 24 разряда. При этом система кодирования обеспечивает однозначное определение 16,5 млн различных цветов, что на самом деле близко к чувствительности человеческого глаза. Режим представления цветной графики с использованием 24 двоичных разрядов называется полноцветным (True Color).

    Каждому из основных цветов можно поставить в соответствие дополнительный цвет, то есть цвет, дополняющий основной цвет до белого. Соответственно дополнительными цветами являются: голубой (Cyan, C), пурпурный (Magenta, M) и желтый (Yellow, Y). Такой метод кодирования принят в полиграфии, но в полиграфии используется еще и четвертая краска – черная (Black, K). Данная система кодирования обозначается CMYK, и для представления цветной графики в этой системе надо иметь 32 двоичных разряда. Такой режим называется полноцветным (True Color).

    Если уменьшать количество двоичных разрядов, используемых для кодирования цвета каждой точки, то можно сократить объем данных, но при этом диапазон кодируемых цветов заметно сокращается. Кодирование цветной графики 16-разрядными двоичными числами называется режимом High Color.

    Кодирование звуковой информации

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

    Метод FM (Frequency Modulation) основан на том, что теоретически любой сложный звук можно разложить на последовательность простейших гармоничных сигналов разной частоты, каждый из которых представляет правильную синусоиду, а следовательно, может быть описан числовыми параметрами, то есть кодом. В природе звуковые сигналы имеют непрерывный спектр, то есть являются аналоговыми. Их разложение в гармонические ряды и представление в виде дискретных цифровых сигналов выполняют специальные устройства – аналогово-цифровые преобразователи (АЦП). Обратное преобразование для воспроизведения звука, закодированного числовым кодом, выполняют цифро-аналоговые преобразователи (ЦАП). При таких преобразованиях часть информации теряется, поэтому качество звукозаписи обычно получается не вполне удовлетворительным и соответствует качеству звучания простейших электромузыкальных инструментов с «окрасом», характерным для электронной музыки.

    Метод таблично-волнового синтеза (Wave-Table) лучше соответствует современному уровню развития техники. Имеются заранее подготовленные таблицы, в которых хранятся образцы звуков для множества различных музыкальных инструментов. В технике такие образцы называются сэмплами. Числовые коды выражают тип инструмента, номер его модели, высоту тона, продолжительность и интенсивность звука, динамику его изменения. Поскольку в качестве образцов используются «реальные» звуки, то качество звука, полученного в результате синтеза, получается очень высоким и приближается к качеству звучания реальных музыкальных инструментов.

    Единицы измерения данных

    Наименьшей единицей измерения информации является байт, равный восьми битам. Одним байтом можно закодировать одно из 256 значений. Существуют и более крупные единицы, такие как килобайт (Кбайт), мегабайт (Мбайт), гигабайт (Гбайт) и терабайт (Тбайт).

    1 байт = 8 бит

    1 Кбайт = 1024 байт

    1 Мбайт = 1024 Кбайт = 220 байт

    1 Гбайт = 1024 Мбайт = 230 байт

    1 Тбайт = 1024 Гбайт = 240 байт

    Данный текст является ознакомительным фрагментом.

    Продолжение на ЛитРес

    Повторение. Информация и ее кодирование

    Введение в информатику

    Введение в информатику Данные в компьютере 2 Как хранятся данные? 3? Как можно знания, находящиеся у вас «в голове», передать другим людям или сохранить для потомков? Кодирование это представление информации

    Подробнее

    Теоретические основы информатики

    Теоретические основы информатики Понятийный аппарат 1. Информация и информатика Информатика это техническая наука, определяющая сферу деятельности, связанную с процессами хранения, преобразования и передачи

    Подробнее

    Кодирование текстовой информации

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

    Подробнее

    Кодирование информации

    Кодирование информации Текст Алфавит => кодировочная таблица Мощность алфавита = количество символов Объем памяти на один символ = количество бит, обеспечивающее необходимое количество вариантов (2 b )

    Подробнее

    log2 P P ИЗМЕРЕНИЕ ИНФОРМАЦИИ

    ИЗМЕРЕНИЕ ИНФОРМАЦИИ Вопрос о количестве информации и методах её измерения не так прост, как кажется на первый взгляд. Если при кодировании текста использовать набор символов ASCII, то для представления

    Подробнее

    N=2 i i Информационный вес символа, бит

    Примеры решения задач по Информатике по темам раздела ИНФОРМАЦИЯ И ИНФОРМАЦИОННЫЕ ПРОЦЕССЫ специальность 20.02.01 1 курс Основы теории В вычислительной технике битом называют наименьшую "порцию" памяти

    Подробнее

    Теоретические сведения

    Практическая работа 1 ОБЩАЯ ХАРАКТЕРИСТИКА И КЛАССИФИКАЦИЯ ТЕХНИЧЕСКИХ СРЕДСТВ ИНФОРМАТИЗАЦИИ Цель: классификация технических средств информатизации, отработка практического навыка решения задач Оборудование:

    Подробнее

    ИНФОРМАЦИЯ. ИЗМЕРЕНИЕ ИНФОРМАЦИИ

    ИНФОРМАЦИЯ. ИЗМЕРЕНИЕ ИНФОРМАЦИИ 7 класс, 2017-2018 учебный год Повторение Информация это сведения об объектах и явлениях окружающей среды. Информатика наука о способах хранения, обработки и передачи информации

    Подробнее

    ПРЕДМЕТ И ОСНОВНЫЕ ПОНЯТИЯ ИНФОРМАТИКИ

    ПРЕДМЕТ И ОСНОВНЫЕ ПОНЯТИЯ ИНФОРМАТИКИ 1 Информатика наука, сложившаяся сравнительно недавно. Её развитие связано с появлением в середине ХХ века электронно-вычислительных машин, которые явились универсальными

    Подробнее

    Информатика 9 класс. Модуль 1

    Информатика 9 класс. Модуль 1 Задание 1 К свойствам информации не относится 1) полнота 2) ценность 3) доступность 4) универсальность Задание 2 Выберете типы информации, обрабатываемые компьютером Выберите

    Подробнее

    Лекция 1. Технологии обработки информации

    Лекция 1 Технологии обработки информации Преподаватели Арбатский Евгений Викторович А517 Федоров Вячеслав Викторович А501 Состав курса Лекции Лабораторные работы Семинары Примерная структура курса 1. Введение.

    Подробнее

    Кодирование текстовой информации

    Кодирование текстовой информации Содержание Вопросы для повторения Двоичное кодирование текстовой информации в компьютере Кодовая таблица Код ASCII Принцип последовательного кодирования алфавита Различные

    Подробнее

    ЗАДАНИЯ - 1. Нумерация разделов по ЕГЭ-2013 ИНФОРМАЦИЯ. А8, А11, В1, В10 СИСТЕМЫ СЧИСЛЕНИЯ. А1, А9, В4, В8 АЛГЕБРА ЛОГИКИ.

    ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ГИМНАЗИЯ 116 ПРИМОРСКОГО РАЙОНА САНКТ-ПЕТЕРБУРГА ЗАДАНИЯ - 1 ИНФОРМАЦИЯ. А8, А11, В1, В10 СИСТЕМЫ СЧИСЛЕНИЯ. А1, А9, В4, В8 АЛГЕБРА ЛОГИКИ. А3,

    Подробнее

    СРЕДСТВА ОБМЕНА ИНФОРМАЦИЕЙ

    СРЕДСТВА ОБМЕНА ИНФОРМАЦИЕЙ на близкое расстояние органы чувств: зрение, слух, речь семафорная азбука язык жестов на далѐкое расстояние сигналы: дым костра, звук рога язык жестов спецназа Код - система

    Подробнее

    ИНФОРМАТИКА ДЕМИН АНТОН ЮРЬЕВИЧ

    ИНФОРМАТИКА ДЕМИН АНТОН ЮРЬЕВИЧ УЧЕБНЫЙ ПЛАН Название раздела/темы Аудиторная работа СРС Лекц Баллы Лаб. Баллы (час.) ии зан. (час.) (час.) 1. Основные понятия и 2 1 0 0 6 определения информатики 2. Представление

    Подробнее

    Алфавитный подход к измерению информации:

    Алфавитный подход к измерению информации: Каждый символ некоторого сообщения имеет определённый информационный вес несёт фиксированное количество информации. Все символы одного алфавита имеют один и тот

    Подробнее

    ТЕОРИЯ. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ Нумерация разделов по ЕГЭ-2013 ИНФОРМАЦИЯ. А8, А11, В1, В10 СИСТЕМЫ СЧИСЛЕНИЯ. А1, А9, В4, В8

    ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ГИМНАЗИЯ 116 ПРИМОРСКОГО РАЙОНА САНКТ-ПЕТЕРБУРГА ТЕОРИЯ. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ - 1.1 ИНФОРМАЦИЯ. А8, А11, В1, В10 СИСТЕМЫ СЧИСЛЕНИЯ. А1, А9, В4,

    Подробнее

    Тема 1 Понятие данных и информации

    Тема 1 Понятие данных и информации 1. Понятие данных и информации 2 Операции с данными 3 Виды и типы данных 4 Кодирование данных двоичным кодом 5 Основные структуры данных 6 Единицы представления, измерения,

    Подробнее

    Информация и еѐ кодирование

    1 Информация и еѐ кодирование Разбор заданий из демонстрационных тестов А1 Считая, что каждый символ кодируется одним байтом, оцените информационный объем следующего предложения из пушкинских строк: Певец

    Подробнее

    Методическое пособие

    Методическое пособие Содержание Понятие информации Источники и приемники информации Передача информации Кодирование Код Числовой способ кодирования Графический способ кодирования Символьный способ кодирования

    Подробнее

    ЕГЭ по информатике Задания КИМ 13

    ЕГЭ по информатике Задания КИМ 13 Раздел 52: Вычисление объёма для хранения массива данных Раздел 53: Информационный объём для хранения автомобильных номеров Раздел 54: Информационный объём для хранения

    Подробнее

    228

    227 228 229 230 231 232 233 234 (Тип: открытый, форма: задание на дополнение) Алгоритм, записанный на языке программирования и выполняемый компьютером называется. Максимальный балл за задание: 3 балла

    Подробнее

    B10 (повышенный уровень, время 3 мин)

    B1 (повышенный уровень, время 3 мин) Тема: Определение скорости передачи информации при заданной пропускной способности канала. Что нужно знать: «физический» аналог задачи: лимонад лимонад сколько лимонада

    Подробнее

    Введение в информатику

    Введение в информатику Информация Слово информация произошло от латинского informatio разъяснение, изложение, осведомление. В философии информация есть отражение реального мира с помощью сведений (сообщений).

    Подробнее

    Индивидуальная работа класс

    Использованная литература МАОУ Лицей 15 1. Информатика. Задачник-практикум в 2 т. / Под ред. И.Г.Семакина, Е.К.Хеннера: Том 1. М.: Бином. Лаборатория знаний, 2004. 304с.: ил. 2. Практикум по информатике

    Подробнее

    Методы кодирования данных 101

    Опубликовано 9 ноября, 2017 автором Брайан Низ

    «Информация» относится к данным, которые были декодированы, согласно программной компании Micro Focus. Это полезная форма данных в реальном мире.

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

    Что такое кодирование данных?

    Компьютеры используют схемы кодирования для хранения и извлечения значимой информации в виде данных.Это известно как кодирование данных.

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

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

    Уровень приложения на первом компьютере отправляет данные для передачи на уровень кодирования / декодирования. Он кодирует данные в поток компьютерных байтов, а аппаратный уровень преобразует байты данных в последовательный поток единиц и нулей, который передается по линии на второй компьютер.Аппаратный уровень второго компьютера преобразует единицы и нули обратно в компьютерные байты, а затем передает их на уровень кодирования / декодирования для декодирования. Байты декодируются обратно в исходный формат и передаются на уровень приложения.

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

      • Как отправляющий компьютер указывает, на какой компьютер он отправляет данные?

      • Если данные будут передаваться через промежуточные устройства, как эти устройства смогут понять, как обрабатывать данные, чтобы они попали в намеченное место назначения?

      • Что делать, если отправляющий и получающий компьютеры используют разные форматы данных и соглашения об обмене данными? Как будут переведены данные, чтобы их можно было обменивать?

    Модель связи, известная как OSI, была разработана Международной организацией по стандартизации для ответа на эти вопросы.OSI контролирует передачу данных в компьютерных сетях. Это не стандарт связи; это руководство для разработки таких стандартов. Модель OSI может помочь объяснить, как данные могут передаваться между двумя подключенными к сети компьютерами.

    Модель семиуровневой OSI

    Управление обменом данными в компьютерной сети слишком сложно для определения одной подзадачи, поэтому модель OSI разделена на семь подзадач. Эти подзадачи соответствуют семи уровням.

    Уровень 1: физический

    Самый нижний уровень модели OSI касается передачи и приема неструктурированного сырого битового потока.Физический уровень описывает электрические / оптические, механические и функциональные интерфейсы с физической средой и передает сигналы для всех более высоких уровней. Согласно Microsoft, он также обеспечивает кодирование данных, подключение к физической среде, функции техники передачи и передачу физической среды.

    Уровень 2: канал передачи данных

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

    Уровень 3: Сеть

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

    Уровень 4: Транспорт

    Транспортный уровень изолирует верхние уровни - уровни с пятого по седьмой, - решая сложность уровней с первого по третий. Однако этот слой различается. «Размер и сложность транспортного протокола зависит от типа услуги, которую он может получить на сетевом уровне», - заявляет Microsoft.«Для надежного сетевого уровня с возможностью виртуального канала требуется минимальный транспортный уровень. Если сетевой уровень ненадежен и / или поддерживает только дейтаграммы, транспортный протокол должен включать расширенное обнаружение ошибок и восстановление ».

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

    Уровень 5: Сессия

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

    Уровень 6: Презентация

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

    Уровень 7: Приложение

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

    Продолжение карьеры в области компьютерных наук

    Кодирование данных - это базовая концепция информатики.Имея онлайн-диплом по информатике в Университете Конкордия в Техасе, вы можете получить знания и навыки, необходимые для успешной карьеры в этой области. По данным Национальной ассоциации колледжей и работодателей, средняя начальная зарплата выпускников факультетов компьютерных наук составляла 78 199 долларов. Эти выпускники также имеют высокий уровень полной занятости (83,9 процента) в течение шести месяцев после получения степени бакалавра.

    Учитесь в гибкой и удобной онлайн-среде с расписанием, которое соответствует вашей жизни.

    Определение кодировки

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

    Медиа-файлы часто кодируются для экономии места на диске. Кодируя цифровые аудио-, видео- и графические файлы, их можно сохранять в более эффективном сжатом формате.Закодированные файлы мультимедиа обычно аналогичны по качеству исходным несжатым файлам, но имеют гораздо меньшие размеры. Например, аудиофайл WAVE (.WAV), преобразованный в файл MP3 (.MP3), может быть 1/10 размера исходного файла WAVE. Точно так же сжатый видеофайл MPEG (.MPG) может потребовать только часть дискового пространства, как исходный файл цифрового видео (.DV).

    Кодировка символов - это еще один тип кодирования, при котором символы кодируются как байты. Поскольку компьютеры распознают только двоичные данные, текст должен быть представлен в двоичной форме.Это достигается путем преобразования каждого символа (который включает буквы, числа, символы и пробелы) в двоичный код. Общие типы кодировки текста включают ASCII и Unicode.

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

    Обновлено: 23 сентября 2010 г.

    TechTerms - Компьютерный словарь технических терминов

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

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

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

    Подписаться

    Encoding Literacy in Computer Science

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

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

    Мы хотели, чтобы его ученики думали и читали как программисты, поэтому мы сосредоточились на вычислительной грамотности, которая, по словам Брюса Шерина из Северо-Западного университета, «требует умения программировать на каком-то уровне». Студенты должны понимать, как работают компьютерные программы, чтобы заложить основу для изучения программирования. К счастью, вычислительная грамотность доступна даже людям, не имеющим подготовки в области информатики, потому что эти концепции отражаются в реальных ситуациях и в решении общих проблем.

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

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

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

    Чтение литературы и чтение других текстов

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

    Переход к информационному тексту необходим и незаменим и должен произойти гораздо раньше. По словам Тимоти Шанахана из Университета Иллинойса в Чикаго, «80 процентов обучения чтению литературы может улучшить успеваемость учащихся на уроках английского языка, но как насчет социальных наук, естественных наук и математики?» Да, а как насчет этих дисциплин - и компьютерного программирования? Новые навыки грамотности заставляют нас думать иначе, чем в последовательности рассказов.

    Сила направлений

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

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

    Кроме того, я попросил студентов записывать слова, которые они не могли расшифровать из контекста, и составить список в раздаточном материале «Сложный словарный запас».

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

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

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

    Понимание кодировки символов - GeeksforGeeks

    Вы когда-нибудь представляли, как компьютер может понимать и отображать то, что вы написали? Вы когда-нибудь задумывались, что означают UTF-8 или UTF-16, когда вы проходите через некоторые конфигурации? Только подумайте, как компьютер должен интерпретировать «HeLLo WorlD».
    Все мы знаем, что компьютер хранит данные в битах и ​​байтах. Итак, для отображения символа на экране или отображения символа в виде байта в памяти компьютера необходим стандарт.Прочтите следующее:

     \ x48 \ x65 \ x4C \ x4C \ x6F \ x20 \ x57 \ x6F \ x72 \ x6C \ x44 

    Это то, что вам покажет память. Как узнать, какой символ задает каждый байт памяти?

    Вот кодировка символов на картинке:

    Если вы еще не догадались - это «HeLLo WorlD» в UTF-8 для вас. И да, мы продолжим читать о UTF-8. Но начнем с ASCII. Большинство из вас, кто занимался программированием или работал со строками, должно быть, знали, что такое ASCII.Если нет, давайте определим, что такое ASCII.
    ASCII: ASCII означает Американский стандартный код для обмена информацией. Компьютеры могут понимать только числа, поэтому код ASCII - это числовое представление символа, такого как «a» или «@», или какого-либо действия. ASCII был разработан давно, и теперь непечатаемые символы редко используются по своему первоначальному назначению.

    Просто посмотрите на следующее -



    9018 9018 9018 9018 9018 9018 9018 9018
    Шестнадцатеричный Десятичный Символ
    \ x48 110 H
    \ x4c 114 L

    И так далее.Вы можете посмотреть таблицу и отображение ASCII на http://www.asciitable.com/. Если вы еще не смотрели таблицу, я порекомендую вам сделать это сейчас! Вы заметите, что это простой набор английских слов и знаков препинания.

    Теперь предположим, что я хочу написать следующие символы:

    A
    B? @

    Это будет интерпретировано моим декодером как 0x410x0a0x200x420x3f0x40 в шестнадцатеричном формате и 065010031666063064 0x20), а следующая строка (0x0a) имеет значение байта или область памяти.

    Разные страны, языки, но потребность, которая их объединила

    Сегодня Интернет сблизил мир. И люди во всем мире не говорят только по-английски, верно? Возникла потребность в расширении этого пространства. Если вы создали приложение и видите, что люди во Франции хотят его использовать, поскольку вы видите в нем большой потенциал. Разве не было бы неплохо просто поменять язык, но с той же функциональностью?

    Почему бы не создать универсальный код в сокращенном виде Unicode для всех ??

    Итак, появился Unicode с действительно хорошей идеей.Каждому символу, в том числе на разных языках, был присвоен уникальный номер, называемый Code Point. Одним из преимуществ Unicode перед другими возможными наборами является то, что его первые 256 кодовых точек идентичны ASCII. Таким образом, для программного обеспечения / браузера проще кодировать и декодировать символы большинства живых языков, используемых на компьютерах. Он стремится быть и в значительной степени уже является надмножеством всех других кодированных наборов символов.


    Юникод также является набором символов (не кодировкой).Он использует те же символы, что и стандарт ASCII, но расширяет список дополнительными символами, что дает каждому символу точку кода. Он стремится содержать всех персонажей (и популярных иконок), используемых во всем мире.

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

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

    Вы когда-нибудь задумывались, что такое UTF-8 или UTF-16 ??

    UTF-8: UTF-8 действительно является доминирующей кодировкой символов во всемирной паутине с 2009 года, и по состоянию на июнь 2017 года ее насчитывается 89.4% всех веб-страниц. UTF-8 кодирует каждую из 1112 064 действительных кодовых точек в Unicode, используя от одного до четырех 8-битных байтов. Точки кода с более низкими числовыми значениями, которые, как правило, встречаются чаще, кодируются с использованием меньшего количества байтов. Первые 128 символов Unicode, которые взаимно однозначно соответствуют ASCII, кодируются с использованием одного октета с тем же двоичным значением, что и ASCII, так что действительный текст ASCII также является действительным Unicode в кодировке UTF-8.

    Итак, сколько байтов к каким символам в этих кодировках дает доступ?
    UTF-8:
    1 ​​байт: стандартный ASCII
    2 байта: арабский, иврит, большинство европейских сценариев (в первую очередь, за исключением грузинского)
    3 байта: BMP
    4 байта: все символы Unicode

    UTF-16:
    2 байта: BMP
    4 байта: все символы Unicode

    Итак, я упомянул BMP.Что это такое?

    Basic Multilingual Plane (BMP) содержит символы почти всех современных языков и большое количество символов. Основная цель BMP - поддержка унификации предшествующих наборов символов, а также символов для письма.

    UTF-8, UTF-16 и UTF-32 - это кодировки, которые применяют таблицу символов Юникода. Но у каждого из них есть немного другой способ их кодирования. UTF-8 будет использовать только 1 байт при кодировании символа ASCII, давая тот же результат, что и любая другая кодировка ASCII.Но для других символов он будет использовать первый бит, чтобы указать, что за ним последует второй байт. UTF-16 по умолчанию использует 16-битный формат, но это дает вам только 65 тысяч возможных символов, что далеко не достаточно для полного набора Unicode. Поэтому некоторые символы используют пары 16-битных значений. UTF-32 наоборот, он использует большую часть памяти (каждый символ имеет фиксированную ширину 4 байта), что делает его довольно раздутым, но теперь в этом сценарии каждый символ имеет эту точную длину, поэтому манипуляции со строками становятся намного проще. Вы можете вычислить количество символов в строке, просто исходя из длины строки в байтах.Вы не можете этого сделать с UTF-8. Вот как он упрощает размещение всего набора символов для разных языков и помогает людям распространять свои приложения или информацию в мире, просто кодируя / записывая на своем языке, остальное все заботится о Декодер.

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

    Автор статьи Deepa Banerjee . Если вам нравится GeeksforGeeks, и вы хотите внести свой вклад, вы также можете написать статью, используя свой вклад.geeksforgeeks.org или отправьте свою статью по адресу [email protected] Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
    Пожалуйста, напишите комментарий, если вы обнаружите что-то неправильное или хотите поделиться дополнительной информацией по теме, обсужденной выше.

    Методы кодирования ДНК в области вычислений ДНК

    Часть Исследования в области вычислительного интеллекта серия книг (SCI, том 94)

    Резюме

    Биоинформатика изучает сбор, обработку, хранение, распространение, анализ и т. д. биологической информации, чтобы понять значение биологических данных с помощью математики, информатики и биологических методов.Некоторые исследования в области биоинформатики, такие как свойства ДНК и закон Уотсона-Крика, предполагают возможность вычислений с молекулами ДНК. ДНК-вычисления - это новая вычислительная парадигма, которая выполняет параллельные вычисления с молекулами ДНК на основе закона Уотсона-Крика. Процедуру вычисления ДНК можно разделить на три этапа: кодирование информации, вычисление (молекулярные операции) и извлечение раствора. Этап кодирования информации - это первый и самый важный этап, который напрямую влияет на формирование оптимального решения.Методы кодирования информации можно разделить на два класса: методы кодирования информации в графах без весов и методы кодирования информации в графах с весами. Предыдущие исследования, относящиеся к первому классу, такие как метод кодирования Адлемана [1] для задачи направленного гамильтонова пути, метод кодирования Липтона [2] для задачи SAT и метод кодирования Оуянга [3] для задачи максимальной клики, не требуют учета весового представительства в цепях ДНК.Однако есть много практических приложений, связанных с весами. Следовательно, представление веса в цепи ДНК является важным вопросом для расширения возможностей вычислений ДНК для решения задач оптимизации. Нараянан и др. [6] представили метод кодирования веса по длине цепей ДНК. Шин и др. [6] предложили метод кодирования веса по количеству водородных связей в цепи ДНК фиксированной длины. Ямамото и др. [7] предложили метод кодирования веса по концентрациям цепей ДНК.Ли и др. [9] предложили метод кодирования веса по температурам плавления цепей ДНК фиксированной длины. Хан и др. [10, 11] предложили метод кодирования весов с помощью общего линейного графа. Они также предоставили метод кодирования весов [12] с помощью графа относительной длины и несколько улучшенных методов кодирования ДНК [13–16] для задачи о клике максимального веса, задачи коммивояжера, задачи о минимальном остовном дереве и 0 / 1 задача о рюкзаке. В этой главе я собираю и классифицирую существующие методы кодирования информации в цепях ДНК, которые будут полезны для дальнейших исследований в области вычислений ДНК.

    Ключевые слова

    Задача коммивояжера Задача о рюкзаке Взвешенный граф Гамильтонов путь Дополнительный код

    Эти ключевые слова были добавлены машиной, а не авторами. Это экспериментальный процесс, и ключевые слова могут обновляться по мере улучшения алгоритма обучения.

    Это предварительный просмотр содержимого подписки,

    войдите в

    , чтобы проверить доступ.

    Предварительный просмотр

    Невозможно отобразить предварительный просмотр. Скачать превью PDF.

    Ссылки

    1. 1.

      Адлеман Л. М. (1994) Молекулярное вычисление решений комбинаторных задач. Science 266: 1021–1024

      CrossRefGoogle Scholar
    2. 2.

      Lipton R J (1995) Решение сложных вычислительных задач с помощью ДНК. Science 268: 542–545

      CrossRefGoogle Scholar
    3. 3.

      Оуян К., Каплан П. Д., Лю С. и др. (1997) Решение задачи максимальной клики с помощью ДНК. Science 278: 446–449

      CrossRefGoogle Scholar
    4. 4.

      Head T, Rozenberg G, Bladergroen R S. и др. (2000) Вычисления с ДНК путем работы с плазмидами.Biosystems 57: 87–93

      CrossRefGoogle Scholar
    5. 5.

      Сакамото К., Гоузу Х., Комия К. и др. (2000) Молекулярные вычисления путем образования шпильки ДНК. Science 288: 1223–1226

      CrossRefGoogle Scholar
    6. 6.

      Нараянан А., Зорбалас С. и др. (1998) Алгоритмы ДНК для вычисления кратчайших путей. В: Proceedings of the Genetic Programming, Morgan Kaufmann 718–723

      Google Scholar
    7. 7.

      Шин С. И, Чжан Б. Т., Джун С. С. и др. (1999) Решение задач коммивояжера с помощью молекулярного программирования.В: Материалы Конгресса по эволюционным вычислениям. IEEE Press 994–1000

      Google Scholar
    8. 8.

      Ямамото М., Мацуура Н., Шиба Т. и др. (2002) Решение задач кратчайшего пути с помощью контроля концентрации. Лекционные заметки по информатике 2340: 203–212

      CrossRefMathSciNetGoogle Scholar
    9. 9.

      Ли Дж. Й, Шин С. И, Парк Т. Х. и др. (2004) Решение задач коммивояжера с молекулами ДНК, кодирующими числовые значения. BioSystems 78: 39–47

      CrossRefGoogle Scholar
    10. 10.

      Хан А., Чжу Д. (2006) Весовой метод кодирования ДНК для задачи китайского почтальона. В: Материалы Конгресса IEEE 2006 г. по эволюционным вычислениям. IEEE Press 2696–2701

      Google Scholar
    11. 11.

      Хан А., Чжу Д. (2007) Модель вычисления ДНК на основе новой схемы кодирования веса для задачи китайского почтальона. Компьютерные исследования и разработки 44: 1053–1062

      CrossRefMathSciNetGoogle Scholar
    12. 12.

      Хан А. (2006) RLM: новый метод кодирования весов в цепях ДНК.В: Материалы Шестой Международной конференции по гибридным интеллектуальным системам. IEEE Press 118–121

      Google Scholar
    13. 13.

      Хан А., Чжу Д. (2006) Новый подход на основе ДНК к решению проблемы клики максимального веса. Конспект лекций по информатике 4115: 320–327

      CrossRefGoogle Scholar
    14. 14.

      Хань А., Чжу Д. (2006) Новый метод кодирования ДНК для задачи коммивояжера. Конспект лекций по информатике 4115: 328–335

      CrossRefGoogle Scholar
    15. 15.

      Хан А., Чжу Д. (2006) Модель вычисления ДНК для задачи минимального связующего дерева. В: Материалы 8-го Международного симпозиума символьных и числовых алгоритмов для научных вычислений. IEEE Press 372–377

      Google Scholar
    16. 16.

      Хан А. (2006) Модель вычисления ДНК для задачи о рюкзаке 0/1. В: Материалы Шестой Международной конференции по гибридным интеллектуальным системам. IEEE Press 122–125

      Google Scholar
    17. 17.

      Паун Г., Розенберг Г., Саломаа А. (1998) ДНК-вычисления: новые вычислительные парадигмы.Спрингер, Берлин. Перевод Сюй Цзинь, Ван Шудун, Пань Линьцян (2004) Издательство Университета Цинхуа, Пекин

      Google Scholar
    18. 18.

      Сетубал Дж., Мейданис Дж. (1997) Введение в вычислительную молекулярную биологию. Cole Publishing Company, Томсон. перевод Чжу Х. и др. (2003) Science Press, Пекин

      Google Scholar
    19. 19.

      Чжан Б. Т., Шин С. И (1998) Молекулярные алгоритмы для эффективных и надежных вычислений ДНК. В: Генетическое программирование, Морган Кауфманн 735–742

      Google Scholar
    20. 20.

      Сюй Дж., Чжан Л. (2003) Принцип ДНК-компьютера, достижения и трудности (I): биологическая вычислительная система и ее приложения в теории графов. Журнал компьютерных наук и технологий 26: 1–10

      Google Scholar
    21. 21.

      Yin Z (2004) ДНК-вычисления в графической и комбинированной оптимизации. Science Press, Пекин

      Google Scholar
    22. 22.

      Ван Л., Линь И, Ли З (2005) Вычисление ДНК для категории задач специального целочисленного планирования.Компьютерные исследования и разработки 42: 1431–1437

      CrossRefGoogle Scholar
    23. 23.

      Чен З, Ли Х, Ван Л. и др. (2005) Поверхностный алгоритм ДНК для решения проблемы идеального соответствия. Компьютерные исследования и разработки 42: 1241–1246

      CrossRefGoogle Scholar
    24. 24.

      Брайч Р.С., Челяпов Н., Джонсон С. и др. (2002) Решение задачи 3-SAT с 20 переменными на компьютере с ДНК. Science 296: 499–502

      CrossRefGoogle Scholar
    25. 25.

      Lancia G (2004) Модели целочисленного программирования для задач вычислительной биологии. Journal of Computer Science and Technology 19: 60–77

      CrossRefMathSciNetGoogle Scholar
    26. 26.

      Ибрагим З., Цубои Ю., Мухаммад М. С. и др. (2005) Реализация вычисления k-кратчайших путей в ДНК. В: Материалы Конгресса IEEE по эволюционным вычислениям. IEEE press 707–713

      Google Scholar
    27. 27.

      Йоноска Н., Кари С.А., Сайто М. (1998) Графические структуры в вычислениях ДНК.В: Вычисления с помощью биомолекул - теория и эксперименты. Penn State 93–110

      Google Scholar

    Информация об авторских правах

    © Springer-Verlag Berlin Heidelberg 2008

    Авторы и филиалы

    1. 1. Кафедра компьютерных наук и технологий Университета Шандун в Вэйхай Вэйхай, Китай
    2. 2. Школа компьютерных наук TechnologyShandong UniversityJinanChina

    Кодировка символов сейчас

    ASCII и UTF-8 - это две современные системы кодирования текста.Оба они описаны в этом видео с участием Кейтлин Мерри.

    Два стандарта кодирования символов определяют, как символы декодируются из единиц и нулей в текст, который вы видите на экране прямо сейчас, и на разные языки, просматриваемые каждый день во всемирной паутине. Эти два стандарта кодирования - ASCII и Unicode.

    ASCII

    Американский стандартный код для обмена информацией (ASCII) был разработан для создания международного стандарта кодирования латинского алфавита.В 1963 году был принят ASCII, чтобы информация могла интерпретироваться между компьютерами; представляющие нижние и верхние буквы, цифры, символы и некоторые команды. Поскольку ASCII кодируется с использованием единиц и нулей, система счисления с основанием 2, он использует семь битов. Семь битов позволяют 2 в степени 7 = 128 возможных комбинаций цифр для кодирования символа. Поэтому ASCII обеспечил возможность кодирования 128 важных символов:

    Как работает кодирование ASCII

    • Вы уже знаете, как преобразовывать десятичные числа в двоичные
    • Теперь вам нужно преобразовать буквы в двоичные числа
    • Каждому символу соответствует десятичный номер (например, A → 65)
    • ASCII использует 7 бит
    • Мы используем первые 7 столбцов таблицы преобразования для создания 128 различных чисел (от 0 до 127)
    Например, 1000001 дает нам число 65 ( 64 + 1 ), что соответствует букве «А».
    64 32 16 8 4 2 1
    1 0 0 0 0 0 1
    Вот как "HELLO" кодируется в ASCII в двоичном формате:
    Латинский символ ASCII
    H 1001000
    E 1000101
    L 1001100
    L 1001100
    O 1001111
    Давайте применим эту теорию на практике:
    1. Откройте Блокнот или любой другой текстовый редактор, который вы предпочитаете
    2. Введите сообщение и сохраните его, e.грамм. "Данные прекрасны"
    3. Посмотрите размер файла - у меня 18 байт
    4. Теперь добавьте еще одно слово, например "Данные ТАК красивы"
    5. Если вы посмотрите на размер файла еще раз, то увидите, что он изменился - мой файл теперь на 3 байта больше (SO [SPACE]: «S», «O» и пробел)

    Юникод и UTF-8

    Поскольку ASCII кодирует символы в 7-битном формате, переход к 8-битной вычислительной технологии означал, что нужно было использовать один дополнительный бит. С помощью этой дополнительной цифры Extended ASCII закодировал до 256 символов.Однако возникшая проблема заключалась в том, что страны, которые использовали разные языки, делали разные вещи с этой дополнительной возможностью кодирования. Многие страны добавляли свои собственные дополнительные символы, а разные числа представляли разные символы на разных языках. Япония даже создала несколько систем кодирования японского языка в зависимости от оборудования, и все эти методы были несовместимы друг с другом. Поэтому, когда сообщение было отправлено с одного компьютера на другой, полученное сообщение могло стать искаженным и нечитаемым; японские системы кодирования символов были настолько сложными, что даже когда сообщение отправлялось с одного типа японского компьютера на другой, происходило нечто, называемое «моджибаке»: Проблема несовместимых систем кодирования стала более актуальной с изобретением всемирной паутины, поскольку люди обменивались цифровыми документами по всему миру, используя несколько языков.Чтобы решить эту проблему, Консорциум Unicode установил универсальную систему кодирования под названием Unicode . Unicode кодирует более 100000 символов, охватывая все символы, которые вы найдете в большинстве языков. Unicode присваивает каждому символу определенное число, а не двоичную цифру. Но с этим были некоторые проблемы, например:
    1. Для кодирования 100000 символов потребуется около 32 двоичных цифр. Unicode использует ASCII для английского языка, поэтому A по-прежнему 65.Однако при кодировании в 32 бита двоичное представление буквы A будет 000000000000000000000000000000000001000001. Это тратит много ценного пространства!
    2. Многие старые компьютеры интерпретируют восемь нулей подряд (ноль) как конец строки символов. Таким образом, эти компьютеры не отправляли символы, идущие после восьми нулей подряд (они не отправляли бы A, если бы оно было представлено как 000000000000000000000000000000000001000001).
    Метод кодирования Unicode UTF-8 решает следующие проблемы:
    - До 128 символов используется обычное значение ASCII (например, A - 01000001)
    - Для любого символа, превышающего 128, UTF-8 разделяет код на два байта и добавление «110» к началу первого байта, чтобы показать, что это начальный байт, и «10» к началу второго байта, чтобы показать, что он следует за первым байтом.Итак, для каждого символа после числа 128 у вас есть два байта:
      [110xxxxx] [10xxxxxx] 
    И вы просто заполняете двоичный код числа между ними:
      [11000101] [10000101] (это число 325 → 00101000101) 
    Это работает для первых 2048 символов. Для других символов в начале первого байта добавляется еще одна «1» и также используется третий байт:
      [1110xxxx] [10xxxxxx] [10xxxxxx] 
    Это дает вам 16 пробелов для двоичного кода.Таким образом, UTF-8 увеличивается до четырех байтов:
      [11110xxx] [10xxxxxx] [10xxxxxx] [10xxxxxx] 
    Таким образом, UTF-8 позволяет избежать проблем, упомянутых выше, а также необходимости индекса и позволяет декодировать символы из двоичной формы в обратном направлении (т.е. он обратно совместим).

    Активы в классе

    Есть много забавных занятий для обучения кодированию символов. Ниже мы включили два упражнения, которые вы можете попробовать в своем классе. Какие главные советы вы можете дать по обучению кодировке символов? Делитесь ими в комментариях!
    • Перевод секретных сообщений : опубликуйте короткое секретное сообщение в ASCII в разделе комментариев, а также переводите сообщения ASCII других участников или отвечайте на них.
    • Бинарные браслеты : создавайте браслеты с использованием бусин разного цвета для обозначения единиц и нулей и написания инициалов или имени в кодировке ASCII.
    Кодирование

    - Сжатие - Полевое руководство по информатике

    Кодирование длин серий (RLE) - это метод, который не так широко используется в наши дни, но это отличный способ почувствовать некоторые проблемы, связанные с использованием сжатия.

    Представьте, что у нас есть следующее простое черно-белое изображение.

    Один очень простой способ, которым компьютер может сохранить это изображение в двоичном формате, - использовать формат, в котором «0» означает белый, а «1» означает черный (это «растровое изображение», потому что мы сопоставили пиксели со значениями битов ). Используя этот метод, изображение выше будет представлено следующим образом:

     011000010000110
    100000111000001
    000001111100000
    000011111110000
    000111111111000
    001111101111100
    011111000111110
    111110000011111
    011111000111110
    001111101111100
    000111111111000
    000011111110000
    000001111100000
    100000111000001
    011000010000110
     
    Формат файлов PBM

    Существует формат изображения, в котором используется только что описанное простое представление «один символ на пиксель».Этот формат называется «переносимым растровым форматом» (PBM). Файлы PBM сохраняются с расширением файла «.pbm» и содержат простой заголовок, за которым следуют данные изображения. Данные в файле можно просмотреть, открыв его в текстовом редакторе, как при открытии файла .txt, а само изображение можно просмотреть, открыв его в программе просмотра чертежей или изображений, которая поддерживает файлы PBM. (формат не очень хорошо поддерживается, но некоторые программы просмотра и редактирования изображений могут их отображать). Файл PBM для изображения ромба, использованного ранее, будет иметь следующий вид:

     P1
    15 15
    0 1 1 0 0 0 0 1 0 0 0 0 1 1 0
    1 0 0 0 0 0 1 1 1 0 0 0 0 0 1
    0 0 0 0 0 1 1 1 1 1 0 0 0 0 0
    0 0 0 0 1 1 1 1 1 1 1 0 0 0 0
    0 0 0 1 1 1 1 1 1 1 1 1 0 0 0
    0 0 1 1 1 1 1 0 1 1 1 1 1 0 0
    0 1 1 1 1 1 0 0 0 1 1 1 1 1 0
    1 1 1 1 1 0 0 0 0 0 1 1 1 1 1
    0 1 1 1 1 1 0 0 0 1 1 1 1 1 0
    0 0 1 1 1 1 1 0 1 1 1 1 1 0 0
    0 0 0 1 1 1 1 1 1 1 1 1 0 0 0
    0 0 0 0 1 1 1 1 1 1 1 0 0 0 0
    0 0 0 0 0 1 1 1 1 1 0 0 0 0 0
    1 0 0 0 0 0 1 1 1 0 0 0 0 0 1
    0 1 1 0 0 0 0 1 0 0 0 0 1 1 0
     

    Первые две строки - это заголовок.Первая строка определяет формат файла (P1 означает, что файл содержит нули и единицы ASCII). Вторая строка указывает ширину, а затем высоту изображения в пикселях. Это позволяет компьютеру узнать размер и размеры изображения, даже если символы новой строки, разделяющие строки в файле, отсутствовали. Остальные данные - это изображение, как и выше. При желании вы можете скопировать и вставить это представление (включая заголовок) в текстовый файл и сохранить его с расширением файла.pbm. Если у вас есть программа на вашем компьютере, которая может открывать файлы PBM, вы можете просмотреть изображение с ее помощью. Вы даже можете написать программу для вывода этих файлов, а затем отображать их как изображения.

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

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

    Оказывается, можем. Есть много способов сделать это, но в этом разделе мы сосредоточимся на методе, называемом кодированием длины прогона .

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

    Это можно представить следующим образом.

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

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

    В третьем ряду пять белых, пять черных, пять белых.

    Это кодируется как:

    Это означает, что мы получаем следующее представление для первых трех строк.

     1, 2, 4, 1, 4, 2, 1
    0, 1, 5, 3, 5, 1
    5, 5, 5
     

    Вы можете определить, какие другие строки следовали бы этой же системе.

    Представление для остальных строк

    Остальные строки -

     4, 7, 4
    3, 9, 3
    2, 5, 1, 5, 2
    1, 5, 3, 5, 1
    0, 5, 5, 5
    1, 5, 3, 5, 1
    2, 5, 1, 5, 2
    3, 9, 3
    4, 7, 4
    5, 5, 5
    0, 1, 5, 3, 5, 1
    1, 2, 4, 1, 4, 2, 1
     
    Кодирование длины тиража в шоу CS Unplugged

    В этом видео с шоу Computer Science Unplugged изображение, закодированное по длине тиража, декодируется с использованием очень больших пикселей (принтер представляет собой аэрозольный баллончик!).

    Чтобы убедиться, что мы можем отменить процесс сжатия, попробуйте найти исходное представление (нули и единицы) этого (сжатого) изображения.

     4, 11, 3
    4, 9, 2, 1, 2
    4, 9, 2, 1, 2
    4, 11, 3
    4, 9, 5
    4, 9, 5
    5, 7, 6
    0, 17, 1
    1, 15, 2
     

    Что такое изображение? Сколько пикселей было в исходном изображении? Сколько чисел было использовано для обозначения этих пикселей?

    Ответ на изображение выше

    Это изображение из упражнения по представлению изображений CS Unplugged, и решение доступно в упражнении (это чашка с блюдцем).

    Следующая интерактивная программа позволяет вам поэкспериментировать с кодированием длин серий.

    Сколько места мы сэкономили, используя это альтернативное представление, и как мы можем его измерить? Один простой способ учесть это - представить, что вы набираете эти представления, чтобы вы могли представить себе, что каждый из исходных битов хранится как один символ, а каждый из кодов RLE использует символ для каждой цифры и запятой (это немного сырая, но это отправная точка).

    В исходном представлении для представления изображения требовалось 225 цифр (единиц и нулей).Подсчитайте количество запятых и цифр (но не пробелов и новых строк, игнорируйте их) в новом представлении. Это количество символов, необходимое для представления изображения в новом представлении (чтобы убедиться, что вы на правильном пути, первые 3 предоставленные вам строки содержат 29 символов).

    Предполагая, что вы правильно представили новое изображение и правильно подсчитали, вы должны были обнаружить, что в новом изображении 121 символ (дважды проверьте, отличается ли ваш номер).Это означает, что для нового представления требуется всего около 54% ​​от количества символов (вычислено с использованием 121/225). Это значительное сокращение пространства, необходимого для хранения изображения - оно примерно вдвое меньше. Новое представление - это сжатая форма старого.

    Представление кодирования длин серий на практике

    На практике этот метод (с некоторыми дополнительными приемами) можно использовать для сжатия изображений примерно до 15% от их исходного размера.В реальных системах исходное изображение использует только один бит для каждого пикселя для хранения значений черного и белого (а не один символ, который мы использовали для наших расчетов). Однако номера длин серий также хранятся намного более эффективно, опять же с использованием битовых шаблонов, которые занимают очень мало места для представления чисел. Используемые битовые шаблоны обычно основаны на методе, называемом кодированием Хаффмана, но мы вернемся к этому позже.

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

    Использование кодировки длины тиража для себя

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

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

    Разработайте сжатое представление вашего изображения, используя кодирование длин серий, то есть длины серий, разделенные запятыми, как было объяснено выше.

    Теперь дайте копию сжатого представления (коды длин серий, а не исходное несжатое представление) другу или однокласснику вместе с объяснением того, как оно сжимается.Попросите их попробовать нарисовать изображение на бумаге с сеткой. Как только они будут выполнены, сравните их преобразование с вашим оригиналом.

    Представьте, что вы и ваш друг являетесь компьютерами; тем самым вы показали, что изображения, использующие эти системы представлений, можно сжимать на одном компьютере и распаковывать на другом, если у вас есть согласованные стандарты (например, каждая строка начинается с белого пикселя). Очень важно, чтобы алгоритмы сжатия следовали стандартам, чтобы файл, сжатый на одном компьютере, можно было распаковать на другом.

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

    Ваш адрес email не будет опубликован. Обязательные поля помечены *