Еще одна особенность кодов в этой таблице — нечетное количество единиц в каждом из них. Она также позволяет проверить корректность штрихкода — так называемый контроль четности (parity). Группа битов обладает четным паритетом, если в ней четное количество битов-единиц, и нечетным паритетом, если в ней нечетное количество битов-единиц.
Для расшифровки битов в правой части штрихкода применяется таблица.
Правосторонние коды
1110010 = 0
1001110 = 5
1100110 = 1
1010000 = 6
1101100 = 2
1000100 = 7
1000010 = 3
1001000 = 8
1011100 = 4
1110100 = 9
Эти коды дополняют коды из предыдущей таблицы. Там, где в левосторонних кодах был 0, теперь стоит 1, и наоборот. Правосторонние коды всегда начинаются с 1 и заканчиваются 0. Кроме того, число битов 1 в них всегда четное, что можно применять для контроля четности. Вот мы и готовы к расшифровке UPC. С помощью двух приведенных выше таблиц можно определить 11 цифр, зашифрованных на банке Campbell Soup.
0 51000 01251 7
Какая досада! Да, это те самые цифры, что напечатаны под штрихкодом. На самом деле это очень удобно: если сканер по каким-то причинам не смог прочитать код, кассир может ввести его вручную. Вы наверняка видели, как это бывает. Конечно, получается, что весь наш труд по расшифровке штрихкода был напрасным, к тому же никакой секретной информации мы так и не получили: просто 30 вертикальных штрихов превратились в 12 цифр.
Первая цифра (в данном случае 0) характеризует тип кода.
0 означает, что перед нами обычный код UPC. Если код нанесен на упаковку с товаром переменного веса, например с мясом или овощами, он начинается с 2. Товары со скидкой обозначаются цифрой 5.
Следующие пять цифр — код производителя. В нашем примере код 51000 соответствует компании Campbell Soup. Он есть на всех продуктах марки Campbell. За ними следует пятизначный (01251) код конкретного продукта этой компании, в нашем случае код банки с куриным супом. Код продукта информативен лишь в сочетании с кодом производителя. У куриного супа с вермишелью, выпущенного другой компанией, будет другой код продукта, в свою очередь код 01251 может значить нечто совершенно иное у другого производителя.
Вопреки распространенному мнению, в код UPC не включается цена товара. Информация о ней извлекается из компьютерной базы данных, используемой в кассовых аппаратах наряду со сканерами.
Последняя цифра (здесь — 7) называется символом проверки остатка и тоже используется для исключения ошибок. Чтобы проверить его на практике, присвоим букву каждой из первых 11 цифр (наш пример 0 51000 01251).
A BCDEF GHIJK
Теперь вычислим:
3 × (A + C + E + G + I + K) + (B + D + F + H + J).
Вычтем результат из ближайшего большего числа, кратного десяти. Полученное число и будет символом проверки остатка для куриного супа с вермишелью Campbell:
3 × (0 + 1 + 0 + 0 + 2 + 1) + (5 + 0 + 0 + 1 + 5) = 3 × 4 + 11 = 23.
Ближайшее большее число, кратное десяти, — 30. Значит, 30 – 23 = 7.
Это число — результат проверки остатка — напечатано под штрихкодом и зашифровано в нем. Такая проверка — одна из форм избыточности. Если остаток, вычисленный по штрихкоду, не совпадет с остатком, явно указанным в нем, штрихкод будет сочтен недействительным.
Как правило, для представления десятичной цифры от 0 до 9 достаточно четырех бит. В штрихкодах используется по семь бит на цифру. Целыми 95 бит закодировано всего 11 значимых десятичных цифр. Если учесть, что UPC с обеих сторон ограничен пустым пространством, эквивалентным девяти нулевым битам, получается, что во всем штрихкоде 11 цифр закодировано 113 бит, по 10 бит на цифру!
Такая избыточная надежность отчасти требуется для защиты от ошибок. Код товара был бы не слишком полезен, если бы покупатель мог в два счета подправить его фломастером.
Кроме того, UPC удобен, поскольку его можно считывать в обоих направлениях. Если в первых считанных цифрах количество единиц четно, сканер распознает, что код читается справа налево. Для расшифровки правосторонних цифр компьютер использует следующую таблицу.
Правосторонние коды в обратном направлении
0100111 = 0
0111001 = 5
0110011 = 1
0000101 = 6
0011011 = 2
0010001 = 7
0100001 = 3
0001001 = 8
0011101 = 4
0010111 = 9
Вот таблица левосторонних кодов.
Левосторонние коды в обратном направлении
1011000 = 0
1000110 = 5
1001100 = 1
1111010 = 6
1100100 = 2
1101110 = 7
1011110 = 3
1110110 = 8
1100010 = 4
1101000 = 9
Эти 7-битовые коды отличаются от кодов, считываемых слева направо. Никакой путаницы не возникает.
Наше знакомство с кодами началось с азбуки Морзе, состоящей из точек, тире и промежутков между ними. Азбука Морзе, на первый взгляд, имеет мало общего с нулями и единицами, на деле же сводится именно к ним.
Вспомните устройство азбуки Морзе. Тире втрое длиннее точки. Точки и тире в пределах одной буквы разделены паузами продолжительностью в одну точку. Промежутки между буквами по длительности равны одному тире. Слова разделяются паузами в два тире.
Чтобы немного упростить анализ, допустим, что длина тире превышает длину точки не в три, а в два раза. Это означает, что точка соответствует одному единичному биту, а тире — двум единичным битам.
Паузы состоят из нулевых битов.
Вот простейшая таблица с азбукой Морзе из главы 1.
А вот та же таблица, преобразованная в биты.
Обратите внимание: все коды начинаются с 1 и кончаются парой 0, представляющей паузу между буквами в пределах одного слова. Кодом пробела между словами является дополнительная пара 0. Таким образом, на азбуке Морзе фраза Hi there выглядит так.
Представив ее в битах, мы получим нечто очень похожее на срез штрихкода.
В битовом выражении азбука Брайля гораздо проще азбуки Морзе. Шрифт Брайля является 6-битовым кодом. Каждый символ — набор из шести точек, каждая из которых может быть выпуклой или плоской. Как говорилось в главе 3, обычно точки нумеруются от 1 до 6.
Например, вот как записывается шрифтом Брайля слово code, где крайний левый бит соответствует первой позиции, а крайний правый — шестой.
Позже мы узнаем, что с помощью битов можно зашифровать не только коды товаров, чувствительность пленки, художественную ценность фильма, способ наступления британской армии или послание любимой женщине, но и любые слова, изображения, звуки, музыку и кино. В своей основе биты — это числа. Для представления информации в форме битов достаточно пересчитать количество доступных возможностей. Это количество определяет, сколько битов понадобится для того, чтобы присвоить каждой возможности уникальный номер.
Биты также играют важную роль в логике, находящейся на стыке философии и математики; ее главная цель — определение истинности или ложности некоего утверждения. Истину и ложь также можно обозначить через 1 и 0.
Глава 10Логика и переключатели
Что есть истина? Аристотель полагал, что она как-то связана с логикой. Сборник его сочинений под названием «Органон» (датируемый IV веком до н. э.) — самое раннее произведение, где подробно освещается эта тема. Для древних греков логика — средство анализа языка c целью нахождения истины, поэтому она считалась формой философии. Основа логики Аристотеля — силлогизм. Самый известный силлогизм (который фактически отсутствует в работах Аристотеля) формулируется так:
Все люди смертны;
Сократ — человек;
следовательно, Сократ смертен.
В силлогизме из двух считающихся истинными предпосылок выводится заключение.
Смертность Сократа может показаться достаточно очевидной, однако существует множество разнообразных силлогизмов. Рассмотрим следующие две предпосылки, которые предложил математик XIX века Чарльз Доджсон, известный как Льюис Кэрролл:
Все философы логичны;
нелогичный человек всегда упрям.
В данном случае вывод не очевиден. Он формулируется так: «Некоторые упрямые люди не являются философами». Обратите внимание на неожиданное и привносящее неопределенность слово «некоторые».
На протяжении более двух тысяч лет математики боролись с логикой Аристотеля, пытаясь укротить ее с помощью математических символов и операторов. До XIX века ближе всех к решению этой задачи удалось подойти только Готфриду Вильгельму фон Лейбницу (1646–1716), который занимался логикой в молодости, а затем заинтересовался иными вещами, например одновременно с Исааком Ньютоном разработал дифференциальное исчисление (независимо от него)[15]. Затем на сцену вышел Джордж Буль.
Джордж Буль родился в 1815 году в Англии в социуме, где его шансы на успех были очень малы. Поскольку он был сыном башмачника и бывшей горничной, его перспективы не сильно отличались от перспектив его предков по причине жесткой классовой иерархии британского общества. Однако благодаря своему пытливому уму и отцу, который интересовался наукой, математикой и литературой, молодой Джордж получил образование, как правило являющееся привилегией мальчиков из высших классов общества. Он изучал латынь, греческий язык и математику. Ранние работы Буля по математике позволили ему в 1849 году стать первым профессором математики в Королевском колледже Корка.
Несколько математиков в середине 1800-х годов работали над формальным определением логики (среди них особо выделялся Огастес де Морган). Однако именно Буль совершил настоящий концептуальный прорыв: сначала в короткой книге «Математический анализ логики, или Очерк исчисления дедуктивных умозаключений» (1847), затем в гораздо более объемном и амбициозном произведении «Исследование законов мышления, на которых основаны математические теории логики и вероятностей» (1854), которое кратко также называется «Исследование законов мышления». Буль умер в 1864 году в возрасте 49 лет от пневмонии, которую он подхватил, попав под дождь по дороге на лекцию.