Строение исходного кода


Строение исходного кода

Wikimedia Foundation . 2010 .

Смотреть что такое «Исходный код» в других словарях:

Исходный код — Исходные материалы фильма негатив, контратип, контрольная копия фильма, оригинал магнитных фонограмм перезаписи музыки, шумов, видеофонограмма мастер, компакт диск и т.п. Синонимы: текст либо непосредственно выполняется интерпретатором, либо… … Финансовый словарь

ИСХОДНЫЙ КОД — Написанный человеком текст компьютерной программы на каком либо языке программирования Словарь бизнес терминов. Академик.ру. 2001 … Словарь бизнес-терминов

исходный код — — [http://www.iks media.ru/glossary/index.html?gloss >Справочник технического переводчика

исходный код — 3.1.13 исходный код (source code): Компьютерная программа, выраженная в удобной для восприятия человеком форме (язык программирования), которая переводится в машиночитаемую форму (объектный код) перед тем, как она может быть испытана с… … Словарь-справочник терминов нормативно-технической документации

исходный код — язык исходного текста … Толковый переводоведческий словарь

Исходный код (значения) — Исходный код: Исходный код написанный человеком текст компьютерной программы. Исходный код технотриллер режиссёра Данкана Джонса … Википедия

Исходный код (фильм) — У этого термина существуют и другие значения, см. Исходный код. Исходный код Source Code … Википедия

Закрытый исходный код — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете … Википедия

Открытый исходный код — Логотип Open Source Initiative (OSI) Открытое программное обеспечение (англ. open source software) это программное обеспечение с открытым исходным кодом. Исходный код создаваемых программ открыт, то есть доступен для просмотра и изменения. Это… … Википедия

Исходная программа (исходный код) — 48) исходная программа (исходный код) соответствующее представление одного или более процессов, которые могут быть преобразованы программирующей системой в форму, исполняемую оборудованием (объектный код или объектный язык) (категории 6, 7 и 9); … Официальная терминология

Редактор исходного кода

  • Реда́ктор исхо́дного ко́да — текстовый редактор для создания и редактирования исходного кода программ. Он может быть отдельным приложением, или встроен в интегрированную среду разработки (IDE).

Редакторы исходного кода имеют некоторые возможности, упрощающие и ускоряющие написание и изменение кода, такие как:

* проверка правильности расстановки скобок,

* контекстная помощь по коду

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

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

Связанные понятия

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

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

Сравнение программ просмотра метаданных и редакторов метаданных в графических файлах.

О программном обеспечении рассказывает другая статья.Переносимое приложение (также портативное, автономное, и — неточно, в качестве кальки — портированное; англ. portable application, portable app) — программное обеспечение, которое для своего запуска не требует процедуры установки и может полностью храниться на съёмных носителях информации, что позволяет использовать данное ПО на многих компьютерах. Переносимое приложение может быть настроено так, чтобы считывать свои конфигурационные настройки.

Строение исходного кода

Предварительные условия. Прежде чем работать с остальной частью этой главы, вы должны запросить чистые, немодифицированные исходные деревья вашего любимого Web-сервера.
Мы работаем с Apache (доступен с http://www.apache.org) и, конечно, с PHP (доступен с http://www.php.net).

Альтернативно вы можете использовать архивы исходников на CD-ROM, сопровождающим эту книгу. Все примеры в этой книге работают с архивами исходников с CD-ROM; мы не можем гарантировать это для каждой версии, полученной из Net. Однако, поскольку программное обеспечение Open Source разрабатывается очень быстро, велики шансы того, что версии на CD-ROM уже устарели и не имеют всей необходимой функциональности. Если вы не можете получить с соответствующих Web-сайтов официальные архивы для работы, поэкспериментируйте с архивами на CD-ROM.

Убедитесь, что вы можете скомпилировать рабочее окружение PHP самостоятельно!
Мы здесь не углубляемся в этот вопрос, поскольку вы уже изучали базовые возможности в этой главе.

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

После извлечения PHP-архива вы увидите структуру директорий, примерно как на Рисунке 9.2.

Рисунок 27-1. Рисунок 9.2. Структура основных директорий исходного дерева PHP.

В таблице описано содержимое большинства этих директорий.

Директория Содержимое
php-4 Главные исходные файлы PHP и главные header-файлы; здесь вы найдёте все определения API РНР, макросов etc. (это важно).
ext Хранилище динамических и встроенных модулей; по умолчанию это «официальные» модули PHP, которые интегрированы в главное исходное дерево. В PHP 4.0 можно компилировать эти стандартные расширения как динамически загружаемые модули (как минимум те, которые это поддерживают).
pear Директория для хранения классов PHP. На момент написания она была всё ещё в стадии разработки, но здесь делается попытка создания чего-либо подобного CPAN для Perl.
sapi Содержит код для различных абстрактных слоёв сервера.
TSRM Местонахождение «Thread SafeResource Manager» (TSRM) для Zend и PHP.
Zend Местонахождение файла Zend; здесь вы найдёте все определения Zend API, макросов etc. (это важно).

Рассмотрение всех файлов, входящих в пакет PHP выходит за рамки этой главы. Однако вы должны хотя бы кратко просмотреть следующие файлы:


php.h , размещённый в главной директории PHP. Это файл содержит определения большинства макросов и API РНР.

zend.h , размещённый в главной директории Zend. Это файл содержит большинство макросов и определений Zend’а.

zend_API.h , также размещённый в директории Zend, который определяет API Zend’а.


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

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

Пример 3.5

Пусть n=7, k=4, g(x)=x 3 +x 2 +1. Найти кодовую комбинацию s(x), если ее информационная часть описывается полиномом f(x)=x 3 +x+1.

Решение. 1) n-k=7-4=3, тогда f(x)* x n — k = (x 3 +x+1)x 3 = x 6 +x 4 +x 3 .

2) с остатком r(x)=x 2 . 3) Таким образом, искомая кодовая комбинация = x 6 +x 4 +x 3 +x 2 или в двоичном виде 1011100, где левые четыре разряда представляют собой информационные разряды, соответствующие полиному f(x)=x 3 +x+1, а остальные три разряда – контрольные, соответствующие полиному r(x)=x 2 .

Таким образом, выявлено первое свойство образующего полинома g(x), состоящее в том, что все разрешенные комбинации данного кода делятся на него без остатка. Он позволяет выбрать из большого числа комбинаций только те, которые удовлетворяют заданному закону построения кода, т.е. разрешенные. Именно поэтому полином g(x) и называется образующим.

Степень l образующего полинома g(x) не может быть меньше требуемого числа контрольных разрядов n-k. Для упрощения обычно полагают l=n-k. Но не любой полином этой степени может выступать в качестве образующего полинома циклического кода. В качестве таковых могут использоваться только так называемые неприводимые полиномы. Полином называется приводимым, если он может быть представлен в виде произведения полиномов низших степеней, в противном случае полином называется неприводимым. Другими словами, неприводимый полином делится без остатка только на самого себя и на единицу. Неприводимые полиномы играют роль, сходную с простыми числами в теории чисел. Из нескольких неприводимых полиномов данной степени в качестве образующего полинома следует выбирать самый короткий, однако число ненулевых членов g(x) не должно быть меньше требуемого кодового расстояния кода.

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


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

Пример 3.6. Построить образующую матрицу циклического кода (7,4) с образующим полиномом g(x)=x 3 +x+1.

Запишем базовые информационные комбинации

Представим их в виде полиномов

1 x x 2 x 3

Умножим на x n — k =x 3

x 3 x 4 x 5 x 6

Поделим каждый из них на образующий полином и зафиксируем остаток

Частное Остаток

Тогда образующая матрица этого кода может быть представлена следующим образом

или в общем виде

Существует другой способ построения образующей матрицы, базирующийся на основной особенности циклического (n,k)-кода. Первая строка образующей матрицы формируется путем приписывания слева к представленному двоичным кодом образующему полиному k-1 нулей. Каждая следующая строка образуется циклическим сдвигом предыдущей строки на один разряд влево. Для того же образующего полинома g(x)=x 3 +x+1 образующая матрица, построенная таким способом, будет выглядеть следующим образом

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

Метод получения канонической формы проверочной матрицы циклического кода аналогичен рассмотренному ранее общему для групповых кодов методу, т.е.

Тогда для рассматриваемого циклического кода с образующим полиномом g(x)=x 3 +x+1 проверочная матрица будет выглядеть следующим образом

Идея обнаружения ошибок в кодовой комбинации циклического кода основана на сформулированном ранее утверждении, что при отсутствии ошибок принятая кодовая комбинация совпадает с переданной , т.е. Без остатка делится на образующий полином g(x).

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

Следовательно, при делении на g(x) получим

При наличии однократной ошибки в каком либо информационном разряде полиномы ошибок имеют вид:

1 x x 2 x 3

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

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

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

Методы построения кодеров и декодеров таких кодов исследуются в лабораторной работе №8 «Кодеры и декодеры циклических кодов» [1. с. 78-85].

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

Для увеличения кодового расстояния циклического кода может быть использовано преобразование расширения кода, выполняемое за счет введения дополнительных контрольных разрядов. Одним из простейших способов расширения кода является введение одного контрольного разряда общей проверки на четность. В результате, например, циклический код (7,4) с образующим полиномом превратиться в циклический код (8,4) с образующим полиномом , поскольку полином (x+1) является образующим для циклического кода с одним контрольным разрядом, способным обнаруживать все ошибки нечетной кратности. Отсюда (попутно) можно сделать вывод о том, что код с проверкой на четность является циклическим кодом с образующим полиномом (x+1). Полученный расширенный код с d=4 будет обладать такими же корректирующими свойствами, что и аналогичный расширенный код Хэмминга. Можно сделать обобщение, состоящее в том, что для любого кода с нечетным кодовым расстоянием введение общей проверки на четность увеличивает кодовое расстояние на 1.

Если далее над этим кодом выполнить операцию укорочения, состоящую в удалении одного информационного разряда, то получится код (7,3) с d=4 и проверочной матрицей

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

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

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

Если число уравнений, входящих в каждую ортогональную систему, не меньше s, то путем голосования по большинству могут быть исправлены любые ошибок. В самом деле, ошибка в одном символе влияет в силу ортогональности не более чем на одну проверку, следовательно, среди значений символа aj , которые получены из всех s проверок неправильными могут оказаться не более t, т.е. Не более половины уравнений. Тогда, сравнивая значения правых частей проверок, а также значение самого символа aj, можно по большинству значений определить верное значение этого символа. Если при нечетном s имеет место равенство голосов, то ошибка обнаруживается, но не исправляется.

Случай, когда число s проверок в каждой ортогональной системе на единицу меньше кодового расстояния s=d-1 является в известном смысле идеальным. В этом случае голосование позволяет полностью реализовать корректирующие свойства кода. Код, для каждого символа которого существует система из d-1 ортогональных проверок, называется полностью ортогонализируемым.

Именно к таким кодам относится код (7,3), проверочная матрица которого получена ранее в результате последовательных операций расширения и укорочения циклического кода.

Пользуясь ею можно записать систему проверочных уравнений

Суммируя по модулю два второе и третье уравнения и разрешая полученные три уравнения относительно а7, получаем систему

отвечающую сформулированным ранее условиям ортогональности.

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

Анализируя указанным выше способом каждый символ принятой кодовой комбинации можно правильно восстановить посланную кодовую комбинацию, если произошло не более одной ошибки, или обнаружит двойную ошибку. Тем самым полностью реализуются корректирующие способности этого кода, поскольку его кодовое расстояние d=4.

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

1 проверка 2 проверка 3 проверка М

Важнейшие классы других полиномиальных кодов

Циклический код, исправляющий более одной ошибки, т.е. код с d ³ 5, в общем случае можно построить следующим образом:

а) по заданному k определить необходимое для исправления одной ошибки n-k и построить (n,k)-код описанным ранее методом;

б) рассматривая этот (n,k)-код как некорректирующий n-разрядный код, определить количество n1-n дополнительных контрольных разрядов для обеспечения исправления одной ошибки в этом коде и построить тем самым (n1,n)-код;

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

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

Заданными при кодировании с помощью БЧХ-кодов является число ошибок t, которое требуется исправлять, и общая длина кодовой комбинации n. На выбор величины n накладывается ограничение: n=2 f – 1, где f – любое целое число больше нуля. Число информационных символов k и число контрольных символов n-k и их состав подлежат определению.

При заданной величине t кодовое расстояние кода может быть определено следующим образом:

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

Образующий полином g(x) БЧХ-кода находится как наименьшее общее кратное (НОК) так называемых минимальных полиномов до степени 2t-1 или d-2 включительно, т.е. g(x) = НОК [Mi(x)], где i = 1,3,5, . . ., 2t-1 – номера минимальных полиномов. Поскольку минимальные полиномы по определению являются простыми и неприводимыми, то, условившись об отбрасывании возможных одинаковых Mi(x), можно НОК заменить произведением полиномов , число которых в этом произведении L=t, а степень полинома g(x) равна .

Знак нестрогого равенства появился как результат того, что степени некоторых Mi(x) могут быть меньше 2t-1.


Далее можно определить число контрольных разрядов n-k, которое по определению равно степени образующего полинома, т.е. n-k = b, после чего становится возможным и определение числа информационных разрядов k=n-(n-k). Если получившееся k окажется меньше требуемого для передачи заданного объема информации, необходимо перейти к следующему по порядку разрешенному n=2 f – 1 и выбрать для формирования g(x) минимальные полиномы степени f. Далее по описанной ранее методике для обычных циклических кодов при известном g(x) могут быть построены образующая и проверочная матрицы кода и, тем самым, код полностью построен и описан. Минимальные полиномы различных степеней являются справочными данными.

Для декодирования БЧХ-кодов могут быть использованы как алгоритмы анализа остатка от деления и мажоритарного декодирования, так и другие алгоритмы.

Единственным известным на настоящий момент совершенным БЧХ-кодом является БЧХ-код (23,12) с кодовым расстоянием, равным 7, и образующим полиномом g(x)=x 11 + x 9 + x 7 + x 6 + x 5 + x + 1 или g(x)=x 11 + x 10 + x 6 + x 5 + x 4 + x 2 + 1. По имени создателя он получил название кода Голея.

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

Коды максимальной длины

Кодами максимальной длины называются циклические коды с параметрами (2 k -1, k), у которых в качестве образующего полинома выбран проверочный полином, полученный описанным ранее образом. Например, требуется построить код (15,4) максимальной дины. Выбрав по описанным выше правилам примитивный полином четвертой степени, например x 4 + x + 1, найдем для него проверочный полином, который и будет образующим полиномом для кода (15,4) максимальной длины

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

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

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

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

Образующий полином кода Файра определяется выражением

где g(x)— неприводимый полином степени l, причем l>b, где b— длина исправляемого пакета ошибок, а c³2b-1, причем с должно выбираться таким, чтобы оно не делилось нацело на число e=2 l -1. Число контрольных разрядов в кодовой комбинации кода Файра определяется по формуле n-k = c+l, а общее число разрядов в кодовой комбинации n находится как наименьшее общее кратное чисел с и е, т.е. n = НОК(с,е).

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

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

Рисунок 3.2. Сверточный кодер

Сверточные кодеры (и коды) характеризуются скоростью кодирования R=k/n, означающей, что если в каждый момент времени (такт) k символов входного кода поступают в регистр, то за это же время с выхода снимается n символов выходного кода. Для данного примера R=k/n = 1/2, т.е. поступление каждого символа на вход приводит к появлению двух символов на выходе. Другой важнейшей характеристикой является длина кодового ограничения или просто кодовое ограничение, равное числу разрядов регистра m, в связи с чем эту характеристику называют иногда памятью кода. Величина na = m*n называется полной длиной кодового ограничения. Величина полного кодового ограничения характеризует протяженность корреляционных связей в кодированной последовательности для одного информационного символа. Если на вход кодера подавать различные информационные последовательности и каждый раз на длине na выходной последовательности фиксировать ее вес, то минимальный зафиксированный вес даст значение т.н. cвободного кодового расстояния dсв.

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

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

1 такт 2 такт 3 такт 4 такт
Сост. регистра
Т1
Т2

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

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

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

Таким образом, сверточный код, формируемый этим кодером, имеет следующие параметры:

— скорость кодирования R=1/2;

— кодовое ограничение m=3;

— полное кодовое ограничение na=6;

— свободное кодовое расстояние dсв=5.

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

Более удобным является представление в виде т.н. решетчатого графа. Решетчатым называют граф, узлы которого находятся в узлах прямоугольной координатной сетки, т.е. образуют строки и столбцы. Граф полубесконечен справа, т.е. число столбцов полубесконечно. Число узлов в каждом столбце, т.е. число строк конечно и равно , где m — длина кодового ограничения. Конфигурация ребер, соединяющих узлы каждого столбца с узлами столбца справа, одинакова для всего графа. На основании сказанного построим решетчатый граф (рис. 3.3) для кодера, приведенного ранее, условившись, что из двух ребер, выходящих из каждого узла, верхнее соответствует входному символу 0, нижнее – 1.

Рисунок 3.3. Решетчатый граф

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

Развитие теории сверточных кодов происходило в трех направлениях в соответствии с тремя важнейшими методами декодирования сверточных кодов:

— метода декодирования по максимуму правдоподобия;

— метода последовательного декодирования;

— метода порогового декодирования.

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

Задачу декодирования сверточного кода можно рассматривать как задачу нахождения пути на решетчатом графе с помощью некоторых правил декодирования. Как и в случае декодирования блоковых кодов по максимуму правдоподобия целесообразными оказываются попытки выбрать правильный путь, который лучше всего согласуется с принятой последовательностью, т.е. попытки минимизировать вероятность ошибки последовательности. Поскольку с ростом длины последовательности число путей растет экспоненциально, то на первый взгляд задача построения оценки последовательности по максимуму правдоподобия для сверточного кода кажется безнадежной. Однако метод построения такой оценки достаточно легко найти, пытаясь непосредственно вычислить метрику для каждого пути на решетке. Вначале число путей действительно растет экспоненциально с ростом длины последовательности. Однако вскоре появляется возможность исключить из рассмотрения такое число путей в каждой вершине, которое в точности уравновешивает число вновь появившихся путей. Таким образом, оказывается возможным иметь сравнительно небольшой список путей, который всегда будет содержать наиболее правдоподобный путь. Эта итеративная процедура декодирования называется алгоритмом Витерби. Проще всего рассмотреть функционирование алгоритма Витерби на примере уже приведенной решетчатой диаграммы для кода с R = 1/2 и m=3. Заметим, что в ней имеется ровно по два пути, ведущих в каждую вершину уровня 4. Поскольку, начиная с этого уровня, соответствующие пути совпадают, декодер максимального правдоподобия может без потери общности принимать решение соответствующее этой вершине. После того, как это сделано, аналогичная процедура может быть применена к следующему уровню и т.д. Именно таким образом работает алгоритм Витерби. Согласно ему на каждом уровне сравниваются два пути, входящие в каждую вершину, и сохраняется лишь тот из них, метрика которого лучше. В качестве метрики может служить расстояние Хэмминга между принятой последовательностью и кодовыми словами, считываемыми с ребер решетки. Другой путь с худшей метрикой исключается из рассмотрения. Оставшиеся пути называются выжившими. Для рассматриваемого кода с m=3 в каждый момент будет сохраняться не более 4 выживших путей.

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

Тогда работа алгоритма может быть описана следующими фрагментами:

1) принимаемый кадр n символов – 10. Декодер выберет оба пути и определит метрику каждого из них – цифра над узлом;
2) принимаемый кадр 00;
3) принимаемый кадр 00;
4) принимаемый кадр 00;
5) принимаемый кадр 00;
6) принимаемый кадр 00.

Можно заметить, что 5 и 6 кадры аналогичны, т.е. процесс будет повторяться при приеме каждого очередного кадра, поскольку больше ошибок в принятой комбинации нет. Можно также заметить, что метрика нулевого пути лучше всех остальных. Из примера ясно, что выживающие пути могут отличаться друг от друга в течение долгого времени. Однако в данном примере при приеме 6 кадра первые 4 ребра всех путей совпадают. В этот момент согласно алгоритму Витерби принимается решение о переданных символах, т.к. выжившие пути приходят из одной вершины, т.е. соответствуют оному информационному символу, т.е. по 6 кадру можно с максимальным правдоподобием предположить, что передавалась последовательность 00000000, соответствующая декодированной последовательности 0000.

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

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

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

1 R , то в любом последовательном декодере будут возникать серьезные вычислительные трудности, связанные с частыми переполнениями буфера.

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

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

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

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

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

Контрольные вопросы к лекции 11

11-1. Как можно записать кодовую комбинацию в виде полинома?


11-2. Какой полином называется порождающим полиномом кода?

11-3. Что называется полем Галуа?

11-4. Как определяются мультипликативная и аддитивная единицы поля Галуа?

11-5. Как определяются обратный элемент по сложению и обратный элемент по умножению для поля Галуа?

11-6. При каком числе элементов существуют конечные алгебраические поля?

11-7. Какое конечное алгебраическое поле называется простым?

11-8. Какое конечное алгебраическое поле называется расширенным?

11-9. Как выполняется операция сложения кодовых полиномов?

11-10. Как выполняется операция умножения кодовых полиномов?

11-11. Как выполняется операция деления кодовых полиномов?

11-12. Какие коды называются циклическими?

11-13. Как при полиномиальном представлении осуществляется процесс формирования кодовой комбинации циклического кода?

11-14. Какими свойствами должен обладать образующий полином циклического кода?

11-15. Как может быть построена каноническая образующая матрица циклического кода, если задан образующий полином?

11-16. Как может быть построена неканоническая образующая матрица циклического кода, если задан образующий полином?

11-17. Как из неканонической формы образующей матрицы получить каноническую форму?

11-18. Что играет роль синдрома при декодировании циклических кодов?

11-19. Что представляют собой операции кодирования и декодирования при полиномиальном представлении циклических кодов?

11-20. Какие устройства используются для аппаратной реализации операций деления полиномов?

11-21. При каких условиях возможно применение метода мажоритарного декодирования?

11-22. Какая система проверочных уравнений называется ортогональной?

11-23. В чем состоит суть метода мажоритарного декодирования?

11-24. Какие параметры являются исходными при кодировании с помощью БЧХ-кодов?

11-25. Что представляет собой образующий полином БЧХ-кода?

11-26. Какие коды называются кодами максимальной длины?

11-27. Что называется пакетом ошибок?

11-28. Что представляет собой образующий полином кода Файра?

11-29. В чем принципиальное отличие сверточных кодов от блоковых?

11-30. Что называется кодовым ограничением сверточного кода?

11-31. Что называется свободным кодовым расстоянием сверточного кода?

11-32. Чему равно число строк в решетчатом графе?

11-33. Перечислите основные способы декодирования сверточных кодов?

11-34. Какие пути на решетчатом графе при использовании алгоритма Витерби называются выжившими?

11-35. Какой параметр декодера Витерби называется окном декодирования?

11-36. Сколько путей на решетчатом графе отслеживает последовательный декодер?

11-37. Как определяется перекошенное кодовое расстояние в декодере Фано?

11-38. В чем состоит принципиальное отличие декодера Фано от декодера Витерби?

11-39. Какое явление при пороговом декодировании сверточных кодов носит название распространения ошибок?

11-40. Какой метод порогового декодирования сверточных кодов называется дефинитным декодированием?

Лекция 12. Обмен данными на канальном уровне

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше. 8990 — | 7235 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Структура HTML-кода

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

Пример 1. Исходный код веб-страницы

Скопируйте содержимое данного примера и сохраните его в папке c:\www\ под именем example2.html. После этого запустите браузер и откройте файл через пункт меню Файл > Открыть файл (Ctrl+O). В диалоговом окне выбора документа укажите файл example2.html. В браузере откроется веб-страница, показанная на рис. 1.

Рис. 1. Результат примера в браузере

Далее разберём отдельные строки нашего кода.

Элемент (жарг. доктайп) предназначен для указания типа текущего документа — DTD (document type definition, описание типа документа). Это необходимо, чтобы браузер понимал, как следует интерпретировать текущую веб-страницу, ведь HTML существует в нескольких версиях — современный HTML5 или устаревшие HTML4 и XHTML. Чтобы браузер «не путался» и понимал, согласно какому стандарту отображать веб-страницу и необходимо в первой строке кода задавать .


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

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

Открывающий тег определяет начало HTML-документа, внутри него хранится «голова» ( ) и «тело» документа ( ).

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

Национальная библиотека им. Н. Э. Баумана
Bauman National Library

Персональные инструменты

Исходный код

Содержание

История

Самые первые программы для компьютеров, которые могли хранить системные инструкции, были написаны двоичным кодом [Источник 2] с помощью передней панели ЭВМ [Источник 3] . Так как через переднюю панель [Источник 4] можно было ввести только машинный код, который по сути являлся исходным. Совместно с появлением первых компьютеров появился и первый исходный код- перфокарты [Источник 5] . Эти перфокарты вначале программировались на ассемблере [Источник 6] , а в дальнейшем перешли на более совершенный язык Fortran. Когда исходный код был дематериализованы в текстовые файлы, появились текстовые редакторы. Ограниченные возможности компьютеров того времени часто требовали печати исходного кода на непрерывной бумаге.

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

Назначение

Исходный код может быть написан на любом из сотен языков программирования , которые были разработаны. Некоторые из наиболее популярных из них являются C , C ++, COBOL [Источник 7] , Fortran, Java, Perl, PHP , Python и Tcl / Tk [Источник 8] . Исходный код необходим для получения машинного кода. При выполнении инструкций программ, написанных на различных языках программирования, компьютеру необходимо преобразовать удобные для человеческого восприятия операторы в форму, понятную для компьютера. Системное программное обеспечение включает специальную программу, транслирующую текст программ, написанных на различных языках программирования, в машинные коды, которые и выполняются компьютером. Этот вид программного обеспечения называется компилятором или интерпретатором.

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

Другое важное назначение исходного кода — описание программы. Текст программы позволяет восстановить логику ее поведения. Чтобы было легче понимать исходный код, к нему приписывают комментарии. Также исходный код применяется в качестве обучающего материала для начинающих программистов. Его также используют в качестве средства передачи алгоритмов между людьми (например, фрагменты кода в книжках).

Качество

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

  • читаемость кода (также наличие комментариев к коду [Источник 9] );
  • лёгкость в поддержке, тестировании, отладке и устранении ошибок, модификации и портировании;
  • отсутствие замечаний, выводимых компилятором;
  • экономное использование ресурсов: памяти, процессора, дискового пространства;
  • отсутствие «мусора» — неиспользуемых переменных, недостижимых блоков кода, ненужных устаревших комментариев и т. д.;
  • переносимость — возможность использования обработчика (компилятора, интерпретатора, транслятора) разных версий или даже различных ОС;
  • возможность интернационализации [Источник 10] интерфейса.

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

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

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

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

Есть целый ряд специализированных инструментов для создания документов непосредственно из существующего исходного кода, например. Doxygen [Источник 11] . Со знанием грамматики программирования может автоматически определить несколько связей между отдельными элементами. Дополнительная информация и описание импортируются из специальных комментариев , отправленных по каждому пункту.

Юридическая защита

Программные средства, и исходный код, что их сопровождает, как правило, относятся к одной из двух парадигм лицензий: открытое программное обеспечение и несвободное программное обеспечение (или проприетарное). В целом, программное обеспечение является открытым, исходный код свободно используется, распространяется, анализируется и модифицируется, или же проприетарным, если исходный код держится в секрете, или находится в частной собственности и доступ к нему ограничен. Для обеспечения закрытости используются преимущественно положения различных законов об авторском праве, но часто используются также коммерческая тайна и патенты. Кроме того, дистрибутив программы, как правило, приходит с лицензионным соглашением (EULA) [Источник 12] , которое, главным образом, запрещает декомпиляцию [Источник 13] , реинжениринг [Источник 14] , анализ, редактирование, или обход защиты от копирования [Источник 15] . Виды защиты исходного кода (кроме традиционного компилирования в объектный код включают шифрование кода, запутывания кода ( англ. code obfuscation ) [Источник 16] или морфинг кода [Источник 17] . Есть несколько причин , по которым разработчики проприетарного программного обеспечения предпринимают большие усилия , чтобы держать в секрете исходные коды, в том числе опасения , что:

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

Строение исходного кода

22. КОДИРОВАНИЕ ИНФОРМАЦИИ

22.1. Общие сведения

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

В качестве элементов кодируемой информации могут выступать:

— буквы, слова и фразы естественного языка;

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

— ситуации и явления;

Кодовые обозначения могут представлять собой:

— буквы и сочетания букв естественного языка;

— световые и звуковые сигналы;

— набор и сочетание химических молекул;

Кодирование может выполняться в целях:

— удобства хранения, обработки и передачи информации (как правило, закодированная информация представляется более компактно, а также пригодна для обработки и передачи автоматическими программно-техническими средствами);

— удобства информационного обмена между субъектами;

— идентификации объектов и субъектов;

— сокрытия секретной информации;

Кодирование информации бывает одно- и многоуровневым. Примером одноуровневого кодирования служат световые сигналы, подаваемые светофором (красный – стой, желтый – приготовиться, зеленый – вперед). В качестве многоуровневого кодирования можно привести представление визуального (графического) образа в виде файла фотографии. Вначале визуальная картинка разбивается на составляющие элементарные элементы (пикселы), т.е. каждая отдельная часть визуальной картинки кодируется элементарным элементом. Каждый элемент представляется (кодируется) в виде набора элементарных цветов (RGB: англ. red – красный, green – зеленый, blue – синий) соответствующей интенсивностью, которая в свою очередь представляется в виде числового значения. Впоследствии наборы чисел, как правило, преобразуются (кодируются) с целью более компактного представления информации (например, в форматах jpeg, png и т.д.). И наконец, итоговые числа представляются (кодируются) в виде электромагнитных сигналов для передачи по каналам связи или областей на носителе информации. Следует отметить, что сами числа при программной обработке представляются в соответствии с принятой системой кодирования чисел.

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

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

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

22.2. Общедоступные кодовые системы


Применение кодов нашло широкое применение в общественной жизни. Как отмечалось выше, даже сами знаки арифметических и логических операций – это кодовые обозначения. В частности, знак «+» для операции сложения (а также знак «-») придумали в немецкой математической школе «коссистов» (т.е. алгебраистов). Они используются в «Арифметике» Иоганна Видмана, изданной в 1489 г. До этого сложение обозначалось буквой p (plus) или латинским словом et (союз «и»), а вычитание — буквой m (minus). У Видмана символ плюса заменяет не только сложение, но и союз «и» [17]. Если «копать еще глубже», то буква «А» — это кодовое обозначение для соответствующего звука.

В качестве других распространенных кодовых систем можно привести:

— обозначение химических элементов из периодической таблицы Дмитрия Ивановича Менделеева;

— сокращенные наименования дисциплин в расписании занятий студентов.

Ниже приводится описание других общедоступных кодовых систем в целях иллюстрации многообразия их назначения и способов представления кодовых обозначений [17].

Азбука Морзе — способ кодирования символов (букв алфавита, цифр, знаков препинания и др.) с помощью последовательности «точек» и «тире». За единицу времени принимается длительность одной точки. Длительность тире равна трём точкам. Пауза между элементами одного знака — одна точка (около 1/25 доли секунды), между знаками в слове — 3 точки, между словами — 7 точек. Назван в честь американского изобретателя и художника Сэмюэля Морзе.

Русская
буква
Латинская
буква
Код Морзе Русская
буква
Латинская
буква
Код Морзе Символ Код Морзе
A A · — Р R · — · 1 · — — — —
Б B — · · · С S · · · 2 · · — — —
В W · — — Т T 3 · · · — —
Г G — — · У U · · — 4 · · · · —
Д D — · · Ф F · · — · 5 · · · · ·
Е (Ё) E · Х H · · · · 6 — · · · ·
Ж V · · · — Ц C — · — · 7 — — · · ·
З Z — — · · Ч O — — — · 8 — — — · ·
И I · · Ш CH — — — — 9 — — — — ·
Й J · — — — Щ Q — — · — — — — — —
К K — · — Ъ N — — · — — Точка · · · · · ·
Л L · — · · Ы Y — · — — Запятая · — · — · —
М M — — Ь (Ъ) X — · · — · · — — · ·
Н N — · Э E · · — · · ! — — · · — —
О O — — — Ю U · · — — @ · — — · — ·
П P · — — · Я A · — · — Конец связи (end contact) · · — · —

Рис.22.1. Фрагмент азбуки Морзе

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

Любопытный факт связан с изобретателем первой лампочки Томасом Альвой Эдисоном (1847-1931 гг.). Он плохо слышал и общался со своей женой, Мэри Стиуэлл, с помощью азбуки Морзе. Во время ухаживания Эдисон сделал предложение, отстучав слова рукой, и она ответила тем же способом. Телеграфный код стал обычным средством общения для супругов. Даже когда они ходили в театр, Эдисон клал руку Мэри себе на колено, чтобы она могла «телеграфировать» ему диалоги актеров [44].

Код Бодо — цифровой 5-битный код. Был разработан Эмилем Бодо в 1870 г. для своего телеграфа. Код вводился прямо клавиатурой, состоящей из пяти клавиш, нажатие или ненажатие клавиши соответствовало передаче или непередаче одного бита в пятибитном коде. Существует несколько разновидностей (стандартов) данного кода (CCITT-1, CCITT-2, МТК-2 и др.) В частности МТК-2 представляет собой модификацию международного стандарта CCITT-2 с добавление букв кириллицы.

Управляющие символы
Двоичный
код
Десятичный
код
Назначение
01000 8 Возврат каретки
00010 2 Перевод строки
11111 31 Буквы латинские
11011 27 Цифры
00100 4 Пробел
00000 Буквы русские
Буквы, цифры и остальные символы
Двоичный
код
Десятичный
код
Латинская
буква
Русская
буква
Цифры и
прочие символы
00011 3 A А
11001 25 B Б ?
01110 14 C Ц :
01001 9 D Д Кто там?
00001 1 E Е З
01101 13 F Ф Э
11010 26 G Г Ш
10100 20 H Х Щ
00110 6 I И 8
01011 11 J Й Ю
01111 15 K К (
10010 18 L Л )
11100 28 M М .
01100 12 N Н ,
11000 24 O О 9
10110 22 P П
10111 23 Q Я 1
01010 10 R Р 4
00101 5 S С
10000 16 T Т 5
00111 7 U У 7
11110 30 V Ж =
10011 19 W В 2
11101 29 X Ь /
10101 21 Y Ы 6
10001 17 Z З +

Рис.22.2. Стандарт кода Бодо МТК-2

На следующем рисунке показана телетайпная перфолента с сообщением, переданным с помощью кода Бодо.

Рис. 22.3. Перфолента с кодом Бодо

Следует отметить два интересных факта, связанных с кодом Бодо.

1. Сотрудники телеграфной компании AT&T Гильберто Вернам и Мейджор Джозеф Моборн в 1917 г. предложили идею автоматического шифрования телеграфных сообщений на основе кода Бодо. Шифрование выполнялось методом гаммирования по модулю 2.

2. Соответствие между английским и русским алфавитами, принятое в МТК-2, было использовано при создании компьютерных кодировок КОИ-7 и КОИ-8.

ASCII и Unicode.

ASCII (англ. American Standard Code for Information Interchange) — американская стандартная кодировочная таблица для печатных и управляющих символов. Изначально была разработана как 7-битная для представления 128 символов, при использовании в компьютерах на символ выделялось 8 бит (1 байт), где 8-ой бит служил для контроля целостности (бит четности). Позднее, с задействованием 8 бита для представления дополнительных символов (всего 256 символов), например букв национальных алфавитов, стала восприниматься как половина 8-битной. В частности на основе ASCII были разработаны кодировки, содержащие буквы русского алфавита: для операционной системы MS-DOS — cp866 (англ. code page – кодовая страница), для операционной системы MS Windows – Windows 1251, для различных операционных систем – КОИ-8 (код обмена информацией, 8 битов), ISO 8859-5 и другие.

Кодировка ASCII Дополнительные символы
Двоичный
код
Десятичный
код
Символ Двоичный
код
Десятичный
код
Символ Двоичный
код
Десятичный
код
Символ Двоичный
код
Десятичный
код
Символ
00000000 NUL 01000000 64 @ 10000000 128 Ђ 11000000 192 А
00000001 1 SOH 01000001 65 A 10000001 129 Ѓ 11000001 193 Б
00000010 2 STX 01000010 66 B 10000010 130 11000010 194 В
00000011 3 ETX 01000011 67 C 10000011 131 ѓ 11000011 195 Г
00000100 4 EOT 01000100 68 D 10000100 132 11000100 196 Д
00000101 5 ENQ 01000101 69 E 10000101 133 11000101 197 Е
00000110 6 ACK 01000110 70 F 10000110 134 11000110 198 Ж
00000111 7 BEL 01000111 71 G 10000111 135 11000111 199 З
00001000 8 BS 01001000 72 H 10001000 136 11001000 200 И
00001001 9 HT 01001001 73 I 10001001 137 11001001 201 Й
00001010 10 LF 01001010 74 J 10001010 138 Љ 11001010 202 К
00001011 11 VT 01001011 75 K 10001011 139 11001011 203 Л
00001100 12 FF 01001100 76 L 10001100 140 Њ 11001100 204 М
00001101 13 CR 01001101 77 M 10001101 141 Ќ 11001101 205 Н
00001110 14 SO 01001110 78 N 10001110 142 Ћ 11001110 206 О
00001111 15 SI 01001111 79 O 10001111 143 Џ 11001111 207 П
00010000 16 DLE 01010000 80 P 10010000 144 ђ 11010000 208 Р
00010001 17 DC1 01010001 81 Q 10010001 145 11010001 209 С
00010010 18 DC2 01010010 82 R 10010010 146 11010010 210 Т
00010011 19 DC3 01010011 83 S 10010011 147 11010011 211 У
00010100 20 DC4 01010100 84 T 10010100 148 11010100 212 Ф
00010101 21 NAK 01010101 85 U 10010101 149 11010101 213 Х
00010110 22 SYN 01010110 86 V 10010110 150 11010110 214 Ц
00010111 23 ETB 01010111 87 W 10010111 151 11010111 215 Ч
00011000 24 CAN 01011000 88 X 10011000 152 11011000 216 Ш
00011001 25 EM 01011001 89 Y 10011001 153 11011001 217 Щ
00011010 26 SUB 01011010 90 Z 10011010 154 љ 11011010 218 Ъ
00011011 27 ESC 01011011 91 [ 10011011 155 11011011 219 Ы
00011100 28 FS 01011100 92 \ 10011100 156 њ 11011100 220 Ь
00011101 29 GS 01011101 93 ] 10011101 157 ќ 11011101 221 Э
00011110 30 RS 01011110 94 ^ 10011110 158 ћ 11011110 222 Ю
00011111 31 US 01011111 95 _ 10011111 159 џ 11011111 223 Я
00100000 32 01100000 96 ` 10100000 160 11100000 224 а
00100001 33 ! 01100001 97 a 10100001 161 Ў 11100001 225 б
00100010 34 « 01100010 98 b 10100010 162 ў 11100010 226 в
00100011 35 # 01100011 99 c 10100011 163 Ј 11100011 227 г
00100100 36 $ 01100100 100 d 10100100 164 ¤ 11100100 228 д
00100101 37 % 01100101 101 e 10100101 165 Ґ 11100101 229 е
00100110 38 & 01100110 102 f 10100110 166 ¦ 11100110 230 ж
00100111 39 01100111 103 g 10100111 167 § 11100111 231 з
00101000 40 ( 01101000 104 h 10101000 168 Ё 11101000 232 и
00101001 41 ) 01101001 105 i 10101001 169 © 11101001 233 й
00101010 42 * 01101010 106 j 10101010 170 Є 11101010 234 к
00101011 43 + 01101011 107 k 10101011 171 « 11101011 235 л
00101100 44 , 01101100 108 l 10101100 172 ¬ 11101100 236 м
00101101 45 01101101 109 m 10101101 173 ¬ 11101101 237 н
00101110 46 . 01101110 110 n 10101110 174 ® 11101110 238 о
00101111 47 / 01101111 111 o 10101111 175 Ї 11101111 239 п
00110000 48 01110000 112 p 10110000 176 ° 11110000 240 р
00110001 49 1 01110001 113 q 10110001 177 ± 11110001 241 с
00110010 50 2 01110010 114 r 10110010 178 І 11110010 242 т
00110011 51 3 01110011 115 s 10110011 179 і 11110011 243 у
00110100 52 4 01110100 116 t 10110100 180 ґ 11110100 244 ф
00110101 53 5 01110101 117 u 10110101 181 µ 11110101 245 х
00110110 54 6 01110110 118 v 10110110 182 11110110 246 ц
00110111 55 7 01110111 119 w 10110111 183 · 11110111 247 ч
00111000 56 8 01111000 120 x 10111000 184 ё 11111000 248 ш
00111001 57 9 01111001 121 y 10111001 185 11111001 249 щ
00111010 58 : 01111010 122 z 10111010 186 є 11111010 250 ъ
00111011 59 ; 01111011 123 < 10111011 187 » 11111011 251 ы
00111100 60 01111110 126 10111110 190 ѕ 11111110 254 ю
00111111 63 ? 01111111 127 DEL 10111111 191 ї 11111111 255 я

Рис. 22.4. Кодовая страница Windows 1251

Unicode — стандарт кодирования символов, позволяющий представить знаки почти всех письменных языков. Стандарт был предложен в 1991 г. некоммерческой организацией «Консорциум Юникода» (англ. Unicode Consortium, Unicode Inc.). Применение этого стандарта позволяет закодировать большее число символов (чем в ASCII и прочих кодировках) за счет двухбайтового кодирования символов (всего 65536 символов). В документах Unicode могут соседствовать китайские иероглифы, математические символы, буквы греческого алфавита, латиницы и кириллицы.

Коды в стандарте Unicode разделены на несколько разделов. Первые 128 кодов соответствуют кодировке ASCII. Далее расположены разделы букв различных письменностей, знаки пунктуации и технические символы. В частности прописным и строчным буквам русского алфавита соответствуют коды 1025 (Ё), 1040-1103 (А-я) и 1105 (ё).

Шрифт Брайля — рельефно-точечный тактильный шрифт, предназначенный для письма и чтения незрячими людьми. Был разработан в 1824 г. французом Луи Брайлем (Louis Braille), сыном сапожника. Луи в возрасте трёх лет потерял зрение, в результате воспаления глаз, начавшегося от того, что мальчик поранился шорным ножом (подобие шила) в мастерской отца. В возрасте 15 лет он создал свой рельефно-точечный шрифт, вдохновившись простотой «ночного шрифта» капитана артиллерии Шарля Барбье (Charles Barbier), который использовался военными того времени для чтения донесений в темноте.

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

Рис. 22.5. Нумерация точек

Каждому символу соответствует свой уникальный набор выпуклых точек. Т.о. шрифт Брайля представляет собой систему для кодирования 2 6 = 64 символов. Но присутствие в шрифте управляющих символов (например, переход к буквам или цифрам) позволяет увеличить количество кодируемых символов.

Управляющие символы
Символ
шрифта
Брайля
Назначение
Буквы
Цифры
Буквы, цифры и остальные символы
Символ
шрифта
Брайля
Латинские
буквы
Русские
буквы
Цифры
A А 1
B Б 2
C Ц 3
D Д 4
E Е 5
F Ф 6
G Г 7
H Х 8
I И 9
J Ж
K К
L Л
M М
N Н
O О
P П
Q Ч
R Р
S С
T Т
U У
V
W В
X Щ
Y
Z З
Ё
Й
Ш
Ъ
Ы
Ь
Э
Ю
Я
Точка
Запятая
Восклицательный знак
Вопросительный знак
Точка с запятой
Дефис
Пробел

Рис. 22.6. Шрифт Брайля

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

Рис. 22.7. Надпись «Sochi 2014» шрифтом Брайля на золотой медали Параолимпийских игр 2014г.

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

В 1948 г. Бернард Сильвер (Bernard Silver), аспирант Института Технологии Университета Дрекселя в Филадельфии, услышал, как президент местной продовольственной сети просил одного из деканов разработать систему, автоматически считывающую информацию о продукте при его контроле. Сильвер рассказал об этом друзьям — Норману Джозефу Вудланду (Norman Joseph Woodland) и Джордину Джохэнсону (Jordin Johanson). Втроем они начали исследовать различные системы маркировки. Их первая работающая система использовала ультрафиолетовые чернила, но они были довольно дороги, а кроме того, со временем выцветали.

Убежденный в том, что система реализуема, Вудланд покинул Филадельфию и перебрался во Флориду в квартиру своего отца для продолжения работы. 20 октября 1949 г. Вудланд и Сильвер подали заявку на изобретение, которая была удовлетворена 7 октября 1952 г. Вместо привычных нам линий патент содержал описание штрихкодовой системы в виде концентрических кругов.

Рис. 22.8. Патент системы Вудланда и Сильвера с концентрическими кругами, предшественниками современных штрихкодов

Впервые штрихкоды начали официально использоваться в 1974 г. в магазинах г. Трой, штат Огайо [44]. Системы штрихового кодирования нашли широкое применение в общественной жизни: торговля, почтовые отправления, финансовые и судебные уведомления, учет единиц хранения, идентификация личностей, контактная информация (веб-ссылки, адреса электронной почты, телефонные номера) и т.д.

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

Таблица 22.1. Разновидности штрихкодов

Наименование Пример штрих-кода Примечания
Линейные
Universal Product Code, UPC
(универсальный код товара)
(UPC-A) Американский стандарт штрихкода, предназначенный для кодирования идентификатора товара и производителя.
Имеются разновидности:
— UPC-E – кодируются 8 цифр;
— UPC-A – кодируется 13 цифр.
European Article Number, EAN
(европейский номер товара)
(EAN-13) Европейский стандарт штрихкода, предназначенный для кодирования идентификатора товара и производителя.
Имеются разновидности:
— EAN-8 – кодируются 8 цифр;
— EAN 13 – кодируется 13 цифр;
— EAN-128 – кодируется любое количество букв и цифр, объединенных в регламентированные группы.
ГОСТ ИСО/МЭК 15420-2001 «Автоматическая идентификация. Кодирование штриховое. Спецификация символики EAN/UPC (ЕАН/ЮПиСи)».
Code 128
(Код 128)
Включает в себя 107 символов. Из которых 103 символа данных, 3 стартовых, и 1 остановочный символ. Для кодирования всех 128-ми символов ASCII предусмотрено три комплекта символов — A, B и C, которые могут использоваться внутри одного штрихкода.
EAN-128 кодирует информацию по алфавиту Code 128
ГОСТ 30743-2001 (ИСО/МЭК 15417-2000) «Автоматическая идентификация. Кодирование штриховое. Спецификация символики Code 128 (Код 128)».
Двумерные
DataMatrix
(матричные данные)
Максимальное количество символов, которые помещаются в один код — 2048 байт.
ГОСТ Р ИСО/МЭК 16022-2008 «Автоматическая идентификация. Кодирование штриховое. Спецификация символики Data Matrix».
QR-код
(англ. quick response — быстрый отклик)
Квадраты в углах изображения позволяют нормализовать размер изображения и его ориентацию, а также угол, под которым сенсор относится к поверхности изображения. Точки переводятся в двоичные числа с проверкой контрольной суммы.
Максимальное количество символов, которые помещаются в один QR-код:
— цифры — 7089;
— цифры и буквы (латиница) — 4296;
— двоичный код — 2953 байт;
— иероглифы — 1817.
MaxiCode
(максикод)
Размер — дюйм на дюйм (1 дюйм = 2.54 см).
Используется для грузоотправительных и грузоприемных систем.
Может вместить в себя столько же символов, что Code128.
ГОСТ Р 51294.6-2000 «Автоматическая идентификация. Кодирование штриховое. Спецификация символики MaxiCode (Максикод)».
PDF147
(англ. Portable Data File —
переносимый файл данных)
Применяется при идентификации личности, учете товаров, при сдаче отчетности в контролирующие органы и других областях.
Поддерживает кодирование до 2710 символов и может содержать до 90 строк.
Microsoft Tag
(метка Microsoft)
Разработан для распознавания при помощи фотокамер, встроенных в мобильные телефоны.
Может вместить в себя столько же символов, что Code128.
Предназначен для быстрой идентификации и получения на устройство заранее подготовленной информации (веб-ссылки, произвольного текста длиной до 1000 символов, телефонного номера и т.п.), привязанной к коду и хранящейся на сервере компании Microsoft.
Содержит 13 байт плюс один дополнительный бит для контроля четности.

Представление чисел в двоичном виде (в компьютере). Как известно, информация, хранящаяся и обрабатываемая в компьютерах, представлена в двоичном виде. Бит (англ. binary digit — двоичное число; также игра слов: англ. bit — кусочек, частица) — единица измерения количества информации, равная одному разряду в двоичной системе счисления. С помощью бита можно закодировать (представить, различать) два состояния (0 или 1; да или нет). Увеличивая количество битов (разрядов), можно увеличить количество кодируемых состояний. Например, для байта (англ. byte), состоящего из 8 битов, количество кодируемых состояний составляет 2 8 = 256.

Числа кодируются в т.н. форматах с фиксированной и плавающей запятой.

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

Для беззнакового представления все разряды отводятся под представление самого числа. Например, с помощью байта можно представить беззнаковые целые числа от 010 до 25510 (000000002 — 111111112) или вещественные числа с одним десятичным знаком от 0.010 до 25.510 (000000002 — 111111112). Для знакового представления, т.е. положительных и отрицательных чисел, старший разряд отводится под знак (0 – положительное число, 1 – отрицательное).

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

В прямом коде запись положительного и отрицательного числа выполняется так же, как и в беззнаковом представление (за исключение того, что старший разряд отводится под знак). Таким образом, числа 510 и -510 записываются, как 000001012 и 100001012. В прямом коде имеются два кода числа 0: «положительный нуль» 000000002 и «отрицательный нуль» 100000002.

При использовании обратного кода отрицательное число записывается в виде инвертированного положительного числа (0 меняются на 1 и наоборот). Например, числа 510 и -510 записываются, как 000001012 и 111110102. Следует отметить, что в обратном коде, как и в прямом, имеются «положительный нуль» 000000002 и «отрицательный нуль» 111111112. Применение обратного кода позволяет вычесть одно число из другого, используя операцию сложения, т.е. вычитание двух чисел X – Y заменяется их суммой X + (-Y). При этом используются два дополнительных правила:

— вычитаемое число инвертируется (представляется в виде обратного кода);

— если количество разрядов результата получается больше, чем отведено на представление чисел, то крайний левый разряд (старший) отбрасывается, а к результату добавляется 12.

В следующей таблице приведены примеры вычитания.

Таблица 22.2. Примеры вычитания двух чисел с использованием обратного кода


X – Y 5 – 5 6 – 5 5 – 6 5 – (-6)
X2 00000101 00000110 00000101 00000101
Y2 00000101 00000101 00000110 11111001
Замена сложением 5 + (-5) 6 + (-5) 5 + (-6) 5 + 6
Обратный код для вычитаемого (-Y2) 11111010 11111010 11111001 00000110
Сложение 00000101
+
11111010
11111111
00000110
+
11111010
100000000
00000101
+
11111001
11111110
00000101
+
00000110
00001011
Отбрасывание старшего разряда и добавление 12 не требуется 00000000
+
00000001
00000001
не требуется не требуется
Результат -0 1 -1 11

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

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

Таблица 22.3. Представление чисел в различных кодах

Десятичное
представление
Код двоичного представления (8 бит)
прямой обратный дополнительный
127 01111111 01111111 01111111
6 00000110 00000110 00000110
5 00000101 00000101 00000101
1 00000001 00000001 00000001
00000000 00000000 00000000
-0 10000000 11111111
-1 10000001 11111110 11111111
-5 10000101 11111010 11111011
-6 10000110 11111001 11111010
-127 11111111 10000000 10000001
-128 10000000

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

Таблица 22.4. Примеры вычитания двух чисел с использованием дополнительного кода

X – Y 5 – 5 6 – 5 5 – 6 5 – (-6)
X2 00000101 00000110 00000101 00000101
Y2 00000101 00000101 00000110 11111010
Замена сложением 5 + (-5) 6 + (-5) 5 + (-6) 5 + 6
Дополнительный код для вычитаемого (-Y2) 11111011 11111011 11111010 00000110
Сложение 00000101
+
11111011
00000000
00000110
+
11111011
100000001
00000101
+
11111010
11111111
00000101
+
00000110
00001011
Отбрасывание старшего разряда и добавление 12 не требуется 00000001 не требуется не требуется
Результат -0 1 -1 11

Можно возразить, что представление чисел в дополнительных кодах требует на одну операцию больше (после инверсии всегда требуется сложение с 12), что может и не потребоваться в дальнейшем, как в примерах с обратными кодами. В данном случае срабатывает известный «принцип чайника». Лучше сделать процедуру линейной, чем применять в ней правила «Если A то B» (даже если оно одно). То, что с человеческой точки зрения кажется увеличением трудозатрат (вычислительной и временной сложности), с точки зрения программно-технической реализации может оказаться эффективней.

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

2. Формат с плавающей запятой, в основном, используется для вещественных чисел. Число в данном формате представляется в экспоненциальном виде

где e — основание показательной функции;
n — порядок основания;
e n — характеристика числа;
m — мантисса (лат. mantissa — прибавка) – множитель, на который надо умножить характеристику числа, чтобы получить само число.

Например, число десятичное число 350 может быть записано, как 3.5 * 10 2 , 35 * 10 1 , 350 * 10 0 и т.д. В нормализованной научной записи, порядок n выбирается такой, чтобы абсолютная величина m оставалась не меньше единицы, но строго меньше десяти (1 ≤ |m| 2 . При отображении чисел в программах, учитывая, что основание равно 10, их записывают в виде m E ± n, где Е означает «*10^» («…умножить на десять в степени…»). Например, число 350 – 3.5Е+2, а число 0.035 – 3.5Е-2.

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

b bn7 bn6 bn5 bn4 bn3 bn2 bn1 b bm15 bm14 bm13 bm12 bm11 bm10 bm9 bm8 bm7 bm6 bm5 bm4 bm3 bm2 bm1
знак величина знак величина
порядок мантисса

Рис. 22.9. Двоичный формат представления чисел с плавающей запятой

Биты bn± и bm±, означающие знак порядка и мантиссы, кодируются аналогично числам с фиксированной запятой: для положительных чисел «0», для отрицательных – «1». Значение порядка выбирается таким образом, чтобы величина целой части мантиссы в десятичном (и соответственно в двоичном) представлении равнялась «1», что будет соответствовать нормализованной записи для двоичных чисел. Например, для числа 35010 порядок n = 810 = 0010002 (350 = 1.3671875 * 2 8 ), а для 57610 – n = 910 = 0010012 (576 = 1.125 * 2 9 ). Битовое представление величины порядка может быть выполнено в прямом, обратном или дополнительном коде (например, для n = 810 бинарный вид 0010002). Величина мантиссы отображает дробную часть. Для ее преобразования в двоичный вид, она последовательно умножается на 2, пока не станет равной 0. Например,

Рис. 22.10. Пример получения дробной части в бинарном виде

Целые части, получаемые в результате последовательного перемножения, и представляют собой двоичный вид дробной части (0.367187510 = 01011112). Оставшаяся часть разрядов величины мантиссы заполняется 0. Таким образом, итоговый вид числа 350 в формате с плавающей запятой с учетом представления мантиссы в нормализованной записи

1 1 1 1 1 1
знак
+
величина
2 8
знак
+
величина
(1) + 0.3671875
порядок мантисса

Рис. 22.11. Двоичный вид числа 350

В программно-аппаратных реализациях арифметических действий широко распространен стандарт представления чисел с плавающей точкой IEEE 2 754 (последняя редакция «754-2008 — IEEE Standard for Floating-Point Arithmetic»). Данный стандарт определяет форматы с плавающими запятыми для представления чисел одинарной (англ. single, float) и двойной (англ. double) точности. Общая структура форматов

b bni . bn1 bmj . bm1
знак
мантиссы
порядок величина
мантиссы

Рис. 22.12. Общий формат представления двоичных чисел в стандарте IEEE 754

Форматы представления отличаются количеством бит (байт), отводимым для представления чисел, и, соответственно, точностью представления самих чисел.

Таблица 22.5. Характеристики форматов представления двоичных чисел в стандарте IEEE 754

Формат single double
Общий размер, бит (байт) 32 (4) 64 (8)
Число бит для порядка 8 11
Число бит для мантиссы
(без учета знакового бита)
23 52
Величина порядка 2 128 .. 2 -127
(±3.4 * 10 38 .. 1.7 * 10 -38 )
2 1024 .. 2 -1023
(±1.8 * 10 308 .. 9.0 * 10 -307 )
Смещение порядка 127 1023
Диапазон представления чисел
(без учета знака)
±1.4 * 10 -45 .. 3.4 * 10 38 ±4.9 * 10 -324 .. 1.8 * 10 308
Количество значащих цифр числа
(не более)
8 16

Особенностью представления чисел по стандарту IEEE является отсутствие бита под знак порядка. Несмотря на это, величина порядка может принимать как положительные значения, так и отрицательные. Этот момент учитывается т.н. «смещением порядка». После преобразования двоичного вида порядка (записанного в прямом коде) в десятичный от полученной величины отнимается «смещение порядка». В результате получается «истинное» значения порядка числа. Например, если для числа одинарной точности указан порядок 111111112 (= 25510), то величина порядка на самом деле 12810 (= 25510 — 12710), а если 000000002 (= 010), то -12710 (= 010 — 12710).

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

C учетом вышеизложенного, число 35010 в формате одинарной точности стандарта IEEE 754 записывается следующим образом.

1 1 1 1 1 1 1 1 1
знак
мантиссы
+
порядок
2 8 (8 = 135 — 127)
величина мантиссы
(1) + 0.3671875

Рис. 22.13. Двоичный вид числа 350 по стандарту IEEE

К другим особенностям стандарта IEEE относится возможность представления специальных чисел. К ним относятся значения NaN (англ. Not a Number — не число) и +/-INF (англ. Infinity — бесконечность), получающихся в результате операций типа деления на ноль. Также сюда попадают денормализованные числа, у которых мантисса меньше единицы.

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

0.0
1.7
3.4
5.1
6.8
8.5
10.2
11.899999999999999
13.599999999999998
15.299999999999997
16.999999999999996
18.699999999999996
20.399999999999995
22.099999999999994
23.799999999999994
25.499999999999993
27.199999999999992
28.89999999999999
30.59999999999999
32.29999999999999
33.99999999999999
35.699999999999996
37.4
39.1
40.800000000000004
42.50000000000001
44.20000000000001
45.90000000000001
47.600000000000016

Рис. 22.14. Результат последовательного добавления числа 1.7 (Java 7)

Другой нюанс обнаруживается при сложении двух чисел, у которых значительно отличается порядок. Например, результатом сложения 10 10 + 10 -10 будет 10 10 . Даже если последовательно триллион (10 12 ) раз добавлять 10 -10 к 10 10 , то результат останется прежним 10 10 . Если же к 10 10 добавить произведение 10 -10 * 10 12 , что с математической точки зрения одно и то же, результат станет 10000000100 (1.0000000100 * 10 10 ).

Генетический код — свойственная всем живым организмам кодированная аминокислотная последовательность белков. Кодирование выполняется при помощи нуклеотидов 3 , входящих в состав ДНК (дезоксирибонуклеиновой кислоты). ДКН — макромолекула, обеспечивающая хранение, передачу из поколения в поколение и реализацию генетической программы развития и функционирования живых организмов. Пожалуй, самый главный код в истории человечества.

В ДНК используется четыре азотистых основания — аденин (А), гуанин (G), цитозин (С), тимин (T), которые в русскоязычной литературе обозначаются буквами А, Г, Ц и Т. Эти буквы составляют алфавит генетического кода. В молекулах ДНК нуклеотиды выстраиваются в цепочки и, таким образом, получаются последовательности генетических букв.

Белки практически всех живых организмов построены из аминокислот всего 20 видов. Эти аминокислоты называют каноническими. Каждый белок представляет собой цепочку или несколько цепочек аминокислот, соединенных в строго определенной последовательности. Эта последовательность определяет строение белка, а, следовательно, все его биологические свойства. Синтез белков (т.е. реализация генетической информации в живых клетках) осуществляется на основе информации, заложенной в ДНК. Для кодирования каждой из 20 аминокислот, а также сигнала «стоп», означающего конец белковой последовательности, достаточно трех последовательных нуклеотидов (триплета).

Рис. 22.15. Фрагмент ДНК

2 IEEE (англ. Institute of Electrical and Electronics Engineers) — институт инженеров по электротехнике и электронике.

3 Содержит азотистое основание, соединенное с сахаром, и фосфорную кислоту.

22.3. Секретные кодовые системы

Секретные коды, как и шифры, предназначены для обеспечения конфиденциальности информации. Изначально секретные кодовые системы представляли собой стеганографическую систему, в основе которой лежало подобие жаргонного кода. Они возникли в целях сокрытия имен реальных людей, упоминавшихся в переписке. Это были небольшие списки, в которых в были записаны скрываемые имена, а напротив них — кодовые замены (подстановки). Официальные коды для сокрытия содержания донесений, которыми пользовались папские эмиссары и послы средиземноморских городов-государств, найденные в ранних архивах Ватикана, датируются XIV в. По мере возрастания потребности в безопасности переписки, у представителей городов-государств появились более обширные перечни, которые включали в себя не только кодовые замены имен людей, но и стран, городов, видов оружия, провианта и т.д. В целях повышения защищенности информации к перечням были добавлены шифралфавиты для кодирования слов, не вошедших в перечень, а также правила их использования, базирующиеся на различных стеганографических и криптографических методах. Такие сборники получили название «номенклаторы». С XV и до середины XIX в. они были основной формой обеспечения конфиденциальности информации [43].

Вплоть до XVII столетия в номенклаторах слова открытого текста и их кодовые замены шли в алфавитном порядке, пока французский криптолог Антуан Россиньоль не предложил использовать более стойкие номенклаторы, состоящие из двух частей. В них существовало два раздела: в одном перечислялись в алфавитном порядке элементы открытого текста, а кодовые элементы были перемешаны. Во второй части в алфавитном порядке шли перечни кодов, а перемешанными были уже элементы открытого текста.

Изобретение телеграфа и азбуки Морзе, а также прокладка трансатлантического кабеля в середине XIX в. значительно расширило сферы применения секретных кодов. Помимо традиционных областей их использования (в дипломатической переписке и в военных целях) они стали широко использоваться в коммерции и на транспорте. Секретные кодовые системы того времени в своем названии содержали слово «код» («Код Госдепартамента (1867 г.)», «Американский код для окопов», «Речные коды : Потомак», «Черный код») или «шифр» («Шифр Госдепартамента (1876 г.)», «Зеленый шифр»). Следует отметить, что, несмотря на наличие в названии слова «шифр», в основу этих систем было положено кодирование.

Рис. 22.16. Фрагмент «Шифра Госдепартамента (1899 г.)»

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

Таблица 22.6. Способы обеспечения конфиденциальности информации в секретных кодовых системах

Способ Тип Примечания Примеры
(кодируемое слово – кодовое обозначение)
Замена слова (словосочетания) другим словом произвольной длины стеганографический Аналог — жаргонный код.
Для одного кодируемого слова могли использоваться несколько кодовых обозначений.
1. Номенклатор города Сиены (XV в.): Cardinales (кардинал) – Florenus; Antonello da Furli (Антолло да Фурли) – Forte.


2. Шифр Госдепартамента 1899 г.: Russia (Россия) – Promotes; Cabinet of Russia (Правительство России) – Promptings.

3. Код руководителя службы связи (1871 г.): 10:30 – Anna, Ida; 13th (тринадцатый) – Charles, Mason. Замена слова (словосочетания) символьной строкой фиксированной длины стеганографический Аналог — жаргонный код. 1. Американский код для окопов (1918 г.): Patrol (патруль) – RAL; Attack (атака) – DIT.

2. Код Госдепартамента А-1 (1919 г.): Diplomat (дипломат) – BUJOH; Diplomatic corps (дипломатический корпус) – BEDAC. Замена слова (словосочетания) числом стеганографический Аналог — жаргонный код.
Для одного кодируемого слова могли использоваться несколько кодовых обозначений. 1. Номенклатор Бенджамина Толмаджа (1779 г.): Defense (оборона) – 143; Attack (атака) – 38.

2. Код вещания для торговых судов союзников во Второй мировой войне (BAMS): остров – 36979; порт – 985. Замена слова (словосочетания) набором цифр фиксированной длины стеганографический Аналог — жаргонный код. 1. Американский код для окопов (1918 г.): Patrol (патруль) – 2307; Attack (атака) – 1447.

2. Американский служебный радиокод № 1 (1918 г.): Oil (масло) – 001; Bad (плохой) – 642. Замена букв криптографический Аналоги – шифр однозначной замены, омофонический шифр, полиалфавитный шифр.
В качестве кодового обозначения могли использоваться буквы, числа, графические обозначения.
Применялась для слов, отсутствующих в списке кодируемых. 1. Номенклатор города Сиены (XV в.): q – ; s – .

2. Номенклатор Джеймса Мэдисона (1781 г.): o – 527; p – 941.

3. Американский код для окопов (1918 г.): a – 1332 .. 2795 или CEW .. ZYR. Содержал также 30 алфавитов шифрозамен для перешифрования кодовых обозначений. Замена сочетания букв криптографический Аналог – полиграммный шифр замены.
В качестве кодового обозначения могли использоваться буквы, числа, графические обозначения. 1. Номенклатор города Сиены (XV в.): bb – ; tt – .

2. Номенклатор X-Y-Z (1737 г.): ce – 493; ab – 1194. Использование пустых знаков стеганографический Аналог – пустышечный шифр.
Ничего назначавшие (лат. nihil importantes) символы использовались для запутывания криптоаналитиков. 1. Номенклатор города Сиены (XV в.): , .

2. Речные коды : Потомак (1918 г.): ASY. Использование аддитивных чисел криптографический Аналог – полиалфавитный шифр.
Аддитивное число, добавляемое к числовому кодовому обозначению, служило в качестве переменной части кода (ключа). Шифр Госдепартамента 1876 г.: правило «Horse» (лошадь) в начале сообщения означало, что при кодировании последующих кодовых обозначений использовалось аддитивное число 203; «Hawk» (ястреб) — 100. Перестановка букв (цифр) в кодовых обозначениях криптографический Аналог – шифр блочной одинарной перестановки. Телеграфный код для обеспечения секретности при передаче телеграмм (1870 г.): одно из правил предписывало перестановку последних трех цифр в цифровом кодовом обозначении, состоящем из пяти цифр. Перестановка кодовых обозначений криптографический Аналог – шифр перестановки. Шифр Госдепартамента 1876 г.: правило «Tiger» (тигр) в начале сообщения означало, что раскодированное сообщение надо читать с последнего слова по первое (задом-наперед); «Tapir» (тапир) – меняя местами каждую пару слов (т.е. первое и второе, третье и четвертое и т.д.).

Сочетание различных способов кодирования и перешифровки в кодовой системе было обычной практикой у разработчиков кодов и стало применяться практически с самого начала их появления. Так, еще в номенклаторе, использовавшемся в г. Сиена в XV в., помимо кодовых замен слов, применялись шифралфавиты для замены букв, их удвоенных сочетаний и пустых знаков. Наибольшего расцвета эта практика получила в конце XIX – начале XX вв. В частности в «Шифре Госдепартамента 1876 г.» (англ. Red Book – Красная книга), состоящем из 1200 страниц, и его дополнении «Неподдающийся декодированию код: дополнение к шифру Госдепартамента» применялись:

— кодовые обозначения в виде слов и чисел;

— 30 шифралфавитов для замены букв;

— 50 правил перешифрования, включая аддитивные числа, перестановки кодовых обозначений и их частей.

В дополнении к «Шифру Госдепартамента 1899 г.» (англ. Blue Book – Синяя книга) были описаны еще 25 дополнительных правил перешифрования: изменение направления чтения и записи, прибавление или вычитание чисел, замена кодовых чисел другими кодовыми числами.

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

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

Справка:Режим исходного кода

В визуальном редакторе.

В классическом редакторе.

Режим исходного кода — это режим редактирования в Визуальном редакторе или Классическом редакторе, в котором вы можете использовать викитекст или HTML.

  • В визуальном редакторе кнопка перехода в исходный код находится в выпадающем меню.
  • В классическом редакторе выберите вкладку «Исходный код».

Если вы предпочитаете всегда редактировать в исходном коде, выберите эту опцию по умолчанию на странице настроек, во вкладке «Редактирование».

Атомная энергетика. Ядерные реакторы АЭС. Атомный флот. Ядерное оружие

Высшая математика

Содержание Соглашения по расширениям Макросы Работа с памятью Функции работы с файлами и директориями Работа со строками Сложные типы

Учебник РНР
Назад Вперёд

Предварительные условия. Прежде чем работать с остальной частью этой главы, вы должны запросить чистые, немодифицированные исходные деревья вашего любимого Web-сервера.
Мы работаем с Apache (доступен с http://www.apache.org) и, конечно, с PHP (доступен с http://www.php.net).

Альтернативно вы можете использовать архивы исходников на CD-ROM, сопровождающим эту книгу. Все примеры в этой книге работают с архивами исходников с CD-ROM; мы не можем гарантировать это для каждой версии, полученной из Net. Однако, поскольку программное обеспечение Open Source разрабатывается очень быстро, велики шансы того, что версии на CD-ROM уже устарели и не имеют всей необходимой функциональности. Если вы не можете получить с соответствующих Web-сайтов официальные архивы для работы, поэкспериментируйте с архивами на CD-ROM.

Убедитесь, что вы можете скомпилировать рабочее окружение PHP самостоятельно!
Мы здесь не углубляемся в этот вопрос, поскольку вы уже изучали базовые возможности в этой главе.

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

После извлечения PHP-архива вы увидите структуру директорий, примерно как на Рисунке 9.2.

Рисунок 27-1. Рисунок 9.2. Структура основных директорий исходного дерева PHP.

В таблице описано содержимое большинства этих директорий.

Директория Содержимое
php-4 Главные исходные файлы PHP и главные header-файлы; здесь вы найдёте все определения API РНР, макросов etc. (это важно).
ext Хранилище динамических и встроенных модулей; по умолчанию это «официальные» модули PHP, которые интегрированы в главное исходное дерево. В PHP 4.0 можно компилировать эти стандартные расширения как динамически загружаемые модули (как минимум те, которые это поддерживают).
pear Директория для хранения классов PHP. На момент написания она была всё ещё в стадии разработки, но здесь делается попытка создания чего-либо подобного CPAN для Perl.
sapi Содержит код для различных абстрактных слоёв сервера.
TSRM Местонахождение «Thread SafeResource Manager» (TSRM) для Zend и PHP.
Zend Местонахождение файла Zend; здесь вы найдёте все определения Zend API, макросов etc. (это важно).

Рассмотрение всех файлов, входящих в пакет PHP выходит за рамки этой главы. Однако вы должны хотя бы кратко просмотреть следующие файлы:


php.h , размещённый в главной директории PHP. Это файл содержит определения большинства макросов и API РНР.

zend.h , размещённый в главной директории Zend. Это файл содержит большинство макросов и определений Zend’а.

zend_API.h , также размещённый в директории Zend, который определяет API Zend’а.


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

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

Стиль написания исходного кода

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

Пока стиль еще не выбран и широко не используется, не так важно, какой именно стиль выбрать. К счастью, еще очень давно Линус представил на рассмотрение стиль, который необходимо использовать, и при написании большей части кода сейчас стараются придерживаться именно этого стиля. Подробное описание стиля приведено в файле Documentation/CodingStyl e со свойственным Линусу юмором.

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

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

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

разработке ядра — это размещать открывающую скобку в первой строке, сразу за соответствующим оператором. Закрывающая скобка помещается в первой позиции с новой строки, как в следующем примере.

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

Илон Маск рекомендует:  Что такое код ora_exec
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL