корректирующие коды во вселенной

Можем ли мы жить в компьютерной симуляции?

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

Нил де Грасс Тайсон, директор планетария Хейдена, оценивает шансы на то, что мы — программа на чужом диске — в 50/50. «Думаю, вероятность такого может быть весьма высока», говорит он. Он отметил разрыв между интеллектом человека и шимпанзе, несмотря на то, что более 98% ДНК у нас общая. Возможно, где-то там есть существа, интеллект которых значительно превышает наш. «Мы были бы просто идиотами рядом с ними. Если это так, то я легко могу представить, что все в нашей жизни — лишь плод чьего-то воображения, созданный для чужих развлечений».

Виртуальные сознания

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

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

Кроме того, в физике всплывают идеи из информационной теории. «В моем исследовании обнаружилась очень странная вещь, — говорит Джеймс Гейтс, физик-теоретик из Университета штата Мэриленд. — Я добрался до корректирующих кодов — благодаря им работают браузеры. Как они оказались в уравнениях, которые я изучал о кварках, электронах и суперсимметрии? Это привело меня к осознанию, что я уже не могу назвать людей вроде Макса сумасшедшими».

Скепсис, скепсис

Тем не менее далеко не все собравшиеся согласились с этим утверждением. «Если вы находите ИТ-решение для своих проблем, это может быть простое совпадение, — отметил Тайсон. — Когда вы молоток, каждая проблема похожа на гвоздь».

И статистический аргумент, что большинство сознаний в будущем будут скорее искусственными, нежели биологическими, тоже нельзя принимать за чистую монету, полагает Лиза Рэндалл, физик-теоретик из Гарвардского университета. «В его основе просто нет хорошо определенных вероятностей. Из этого аргумента следует, что есть много сущностей, которые хотят нас имитировать. Но как по мне, это странно. Мы весьма заинтересованы сами в себе. Я не знаю, почему высшие виды хотели бы имитировать нас». Рэндалл также говорит, что не совсем понимает, почему другие ученые вообще интересуются предположением, что наша Вселенная — симуляция. Она считает, что эта идея — ноль без палочки.

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

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

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

Жизнь, Вселенная и все остальное

Но если выяснится, что мы действительно живем в некой «Матрице», что тогда? Ведь мы никуда не денемся.

«Я бы порекомендовал идти и делать что-то интересное, — говорит Тегмарк, — чтобы имитаторы нас не вырубили».

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

И если кто-то создал нашу симуляцию, делает ли это его Богом? «Мы в этой Вселенной можем создавать миры-симуляции, и в этом нет ничего жуткого, — говорит Дэвид Чалмерс, профессор философии в Нью-Йоркском университете. — В нашем создателе тоже нет ничего жуткого». Если взглянуть с другой стороны, то мы и сами боги наших собственных симуляций. Но остается один вопрос: что будет, если обнаружится баг, который выведет из строя всю программу?

Источник

Как пространство и время могут быть квантовым кодом исправления ошибок

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

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

В 1994-м математик из исследовательского подразделения AT&T по имени Питер Шор мгновенно прославил квантовые компьютеры (КК), открыв, что эти гипотетические устройства могли бы быстро раскладывать большие числа на множители – тем самым ломая большую часть современной криптографии. Но на пути реального создания КК стояла фундаментальная проблема: естественная неустойчивость их физических компонентов.

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

Однако кубиты безумно подвержены ошибкам. Слабейшее магнитное поле или случайный микроволновый импульс заставляет их «перебрасывать биты», меняя их шансы оказаться равными |0> или |1> по отношению к другим кубитам, или «переворачивать фазы», что обращает математическое отношение двух их состояний. Чтобы КК смогли работать, учёным нужно найти способы защищать информацию даже при повреждении отдельных кубитов. Более того, эти способы должны обнаруживать и исправлять ошибки, не измеряя сами кубиты напрямую, поскольку измерение приводит к коллапсу сосуществующих возможностей кубита в определённую реальность – а старые добрые 0 и 1 не могут поддерживать квантовые вычисления.

В 1995 году Шор вслед за своим алгоритмом разложения опубликовал ещё одно поразительное доказательство, о существовании «кодов, исправляющих квантовые ошибки». Специалисты по информатике Дорит Ааронова и Майкл Бен-Ор (а также другие независимые исследователи) годом позже доказали, что эти коды теоретически могут довести количество ошибок почти до нуля. «Это было важнейшее открытие 90-х, убедившее людей, что масштабируемые квантовые вычисления в принципе возможны, — сказал Скотт Ааронсон, ведущий специалист по квантовым компьютерам из Техасского университета. – И что это просто сложнейшая инженерная задача».

Питер Шор, Дорит Ааронова и Майкл Бен-Ор

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

Однако в рамках настойчивых поисков этих кодов, проходивших в последние 25 лет, в 2014-м году произошло нечто забавное – физики нашли свидетельство глубоких связей между квантовым исправлением ошибок и природой пространства, времени и гравитации. В общей теории относительности Альберта Эйнштейна гравитация определяется, как искривление ткани пространства и времени – или «пространства-времени» — вокруг массивных объектов. Мяч, подброшенный в воздух, перемещается по прямой линии в пространстве-времени, а оно уже изгибается по направлению к Земле. Однако, несмотря на всю мощь теории Эйнштейна, физики считают, что у гравитации должно быть более глубокое, квантовое происхождение, из которого каким-то образом появляется нечто похожее на ткань пространства-времени.

В 2014-м трое молодых исследователей квантовой гравитации пришли к невероятному результату. Они работали в любимой теоретиками области: игрушечной вселенной, известной, как «антидеситтеровское пространство», которая работает как голограмма. Искривлённая ткань пространства-времени внутри вселенной возникает как проекция запутанных квантовых частиц, существующих на её внешней границе. Ахмед Альмейри, Си Дон и Даниель Харлоу провели вычисления, из которых следует, что это голографическое «проявление» пространства-времени работает точно как квантовый код исправления ошибок. В журнале физики высоких энергий они опубликовали предположение о том, что само пространство-время является кодом – по крайней мере, в антидеситтеровском пространстве. Работа породила целую волну активности в сообществе исследователей квантовой гравитации, и были открыты новые квантовые коды исправления ошибок, включающие в себя больше свойств пространства-времени.

Джон Прескил, физик-теоретик из Калифорнийского технологического института, говорит, что квантовое исправление ошибок объясняет надёжность пространства-времени, несмотря на то, что оно соткано из хрупкого квантового вещества. «Нам не приходится обходиться с этой идеей слишком осторожно, чтобы не развалить геометрию, — сказал Прескил. – Я думаю, эта связь с квантовым исправлением ошибок – глубочайшее объяснение из всех, что у нас есть».

Язык квантового исправления ошибок также начинает позволять исследователям изучать загадки чёрных дыр: сферических участков, в которых пространство-время так сильно искривляется к центру, что оттуда не может убежать даже свет. «Все следы ведут к чёрным дырам», — сказал Альмейри, работающий в данное время в Институте передовых исследований в Принстоне. В этих наполненных парадоксами местах гравитация достигает своего пика, а общая теория относительности Эйнштейна перестаёт работать. «Есть некоторые признаки того, что если мы поймём, какой код использует пространство-время, — сказал он, — это может помочь нам понять внутреннее строение чёрных дыр».

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

Ахмед Альмейри, Си Дон и Даниель Харлоу

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

В качестве простого примера рассмотрим код для трёх кубитов: они использует три «физических» кубита для защиты одного «логического» кубита информации от переворачивания битов. Такой код не особенно полезен для квантового исправления ошибок, поскольку не защищает от переворота фаз, но объясняющую функцию выполняет. Состояние логического кубита |0> соответствует нахождению всех трёх физических кубитов в состоянии |0>, а состояние |1> соответствует тому, что все три находятся в состоянии |1>. Система находится в суперпозиции этих состояний, что записывается, как |000> + |111>. Но, допустим, у одного из кубитов перебросился бит. Как обнаружить и исправить ошибку, не измеряя кубиты напрямую?

В квантовый контур кубит можно ввести через два шлюза. Один проверяет «чётность» первого и второго физических кубитов – одинаковые они или различные – а другой проверяет чётность первого и третьего. Когда ошибок нет (то есть, кубиты находятся в состоянии |000> + |111>), измеряющие чётность шлюзы определяют, что первый и второй, а также первый и третий кубиты идентичны. Однако если у первого кубита случайно перебрасывается бит, это приводит к состоянию |100> + |011>, и шлюз определяет различие в обеих парах. Переброс бита во втором кубите даёт |010> + |101>, шлюзы определяют, что первый и второй кубит отличаются, а второй и третий совпадают; в случае переброса третьего кубита результат будет «совпадают; различаются». Эти уникальные результаты показывают, какая именно корректирующая хирургия необходима, и необходима ли она вообще – то есть, операция переброса назад первого, второго или третьего физического кубита, не приводящая к коллапсу логического кубита. «Квантовое исправления ошибок кажется мне магией», — сказал Альмейри.

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

Важно отметить, что АдС пространство отличается от геометрии пространства-времени нашего, деситтеровского пространства. Наша Вселенная насыщена положительной энергией вакуума, заставляющей её расширяться без границ, в то время, как в АдС пространстве энергия вакуума отрицательна, из-за чего оно приобретает гиперболическую геометрию, похожую на «Предел – круг» М. К. Эшера. Мозаичные существа Эшера становятся всё меньше, распространяясь от центра круга, в итоге исчезая на периметре. Точно так же пространственное измерение, исходящее из центра АдС пространства, постоянно сжимается и в итоге исчезает, обозначая внешнюю границу вселенной. АдС пространство стало популярным у физиков-теоретиков, изучающих квантовую гравитацию, в 1997, после того, как известный физик Хуан Малдасена открыл, что его изогнутая ткань пространства-времени «голографически дуальна» квантовой теории частиц, существующих на границе, свободной от гравитации и с меньшим числом измерений.

Гиперболическая геометрия на гравюре Эшера 1959 года «Предел – круг III» изображает АдС пространство

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

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

Конечно, одна точка – это так себе вселенная. В 2015 году Харлоу, Прескил, Фернандо Паставский и Бени Йошида обнаружили ещё один голографический код, названный HaPPY, перенимающий больше свойств АдС пространства. Код делит пространство на пятисторонние плитки – «как маленькие детальки конструктора Tinkertoy», сказал Патрик Хейден из Стэнфордского университета, руководитель исследований. Каждая деталька представляет одну точку пространства-времени. «Эти плитки играли бы роль рыб в мозаике Эшера», — сказал Хейден.

В коде HaPPY и других открытых голографических схемах исправления ошибок, всё внутри региона пространства-времени, называемого «клином запутанности» [entanglement wedge], можно воссоздать из кубитов, находящихся в регионе, соседнем с границей. У перекрывающиеся регионов на границе будут накладываться клинья запутанности, сказал Хейден, точно так же, как логический кубит в КК можно воссоздать из множества различных подмножеств физических кубитов. «И вот здесь вступает в игру свойство исправления ошибок».

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

Пока что такие исследователи, как Альмейри, Харлоу и Хейден, работают с АдС пространством, поскольку у него много общих черт с деситтеровским миром, но при этом оно легче поддаётся изучению. Геометрии пространства-времени обоих пространств подчиняются теории Эйнштейна, они просто изгибаются в разных направлениях. И что, вероятно, гораздо важнее, во вселенных обоих типов есть чёрные дыры. «Самое фундаментальное свойство гравитации – наличие чёрных дыр», — сказал Харлоу, сейчас работающий адъюнкт-профессором физики в MIT. «Именно это отличает гравитацию от всех остальных взаимодействий. Поэтому с квантовой гравитацией так тяжело».

Язык квантового исправления ошибок обеспечил новый способ описания чёрных дыр. Наличие чёрной дыры определяется, как «отказ исправляемости», сказал Хейден: «Когда у вас появляется так много ошибок, что вы уже не можете отслеживать, что происходит в большом количестве пространства-времени, вы приходите к чёрной дыре. Это что-то типа сливного отверстия для невежества».

Невежество неизбежно накапливается в отношении внутренностей чёрных дыр. Откровение Стивена Хокинга 1974-го года о том, что ЧД излучают тепло, и, следовательно, рано или поздно испаряются, породило печально известный «парадокс исчезновения информации в ЧД», который спрашивает, что происходит со всей проглоченной ЧД информацией. Эта проблема может быть связана с космологией и рождением Вселенной, поскольку расширение сингулярности Большого взрыва очень похоже на гравитационный коллапс ЧД в обратном воспроизведении.

АдС пространство упрощает вопрос об информации. Поскольку граница АдС вселенной голографически дуальна всему, что в ней есть – всем ЧД и прочему – то информация, падающая в ЧД, гарантированно не потеряется; она всегда будет голографически закодирована на границе вселенной. Расчёты показывают, что для реконструкции информации о внутренностях чёрной дыры на основе кубитов на границе, вам потребуется доступ к запутанным кубитам примерно на трёх четвертях границы. «Чуть больше половины уже недостаточно», — сказал Альмейри. Он добавил, что требование трёх четвертей должно сообщать что-то важное о квантовой гравитации, но вопрос о том, почему получается именно такая доля, «всё ещё остаётся открытым».

В первой заявке Альмейри от 2012 года, высокий худой физик из ОАЭ и три его соратника углубили информационный парадокс. Их рассуждения предполагали, что информация вообще может не попадать внутрь ЧД, поскольку её остановит «файервол» на горизонте событий ЧД.

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

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

Физике же ещё придётся разобраться с тем, можно ли описать деситтеровскую вселенную, например, нашу, при помощи голограммы и в терминах кубитов и кодов. «Вся эта связь известна для мира, который очевидно не является нашим», — сказал Ааронсон. В работе от прошлого года Дон, сейчас работающий в Калифорнийском университете в Санта-Барбаре, и его соавторы Ева Сильверстейн и Гонзало Торроба, сделали шаг в деситтеровском направлении, пытаясь создать примитивное голографическое описание. Исследователи пока ещё изучают это предложение, но Прескил считает, что язык квантового исправления ошибок в итоге всё же будет перенесён в реальное пространство-время.

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

Источник

Корректирующие коды. Начало новой теории кодирования

Введение

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

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

Этот путь привел меня к вопросу, а что я уже могу самостоятельно делать без книжных «костылей», имея перед собой только чистый лист бумаги и карандаш с ластиком? Оказалось совсем немного и не совсем то, что было нужно. Пройден был сложный путь бессистемного самообразования. Вопрос был такой. Могу ли я построить и объяснить, прежде всего себе, работу кода, обнаруживающего и исправляющего ошибки, например, код Хемминга, (7, 4)-код?

Известно, что код Хемминга широко используется во многих прикладных программах в области хранения и обмена данными, особенно в RAID; кроме того, в памяти типа ECC и позволяет «на лету» исправлять однократные и обнаруживать двукратные ошибки.

Информационная безопасность. Коды, шифры, стегосообщения

Информационное взаимодействие путем обмена сообщениями его участников должно обеспечиваться защитой на разных уровнях и разнообразными средствами как аппаратными так и программными. Эти средства разрабатываются, проектируются и создаются в рамках определенных теорий (см. рис.А) и технологий, принятых международными договоренностями об OSI/ISO моделях.

Защита информации в информационных телекоммуникационных системах (ИТКС) становится практически основной проблемой при решении задач управления, как в масштабе отдельной личности – пользователя, так и для фирм, объединений, ведомств и государства в целом. Из всех аспектов защиты ИТКС в этой статье будем рассматривать защиту информации при ее добывании, обработке, хранении и передаче в системах связи.

Уточняя далее предметную область, остановимся на двух возможных направлениях, в которых рассматриваются два различных подхода к защите, представлению и использованию информации: синтаксическом и семантическом. На рисунке используются сокращения: кодек–кодер-декодер; шидеш – шифратор-дешифратор; скриз – скрыватель – извлекатель.

Рисунок А – Схема основных направлений и взаимосвязи теорий, направленных на решение задач защиты информационного взаимодействия

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

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

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

В общем «поехали». По определению, а их довольно много, понять что есть код очень даже не просто. Авторы пишут, что код — это алгоритм, отображение и ещё что-то. О классификации кодов я не буду здесь писать, скажу только, что (7, 4)-код блоковый.

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

Поскольку роль сторон переменчива оба этих устройства объединяют в одно и называют сокращенно кодек (кодер/декодер), и устанавливают на обоих концах канала. Дальше, раз есть слова, есть и алфавит. Алфавит — это два символа <0, 1>, в технике массово используются блоковые двоичные коды. Алфавит естественного языка (ЕЯ) — множество символов — букв, заменяющих при письме звуки устной речи. Здесь не будем углубляться в иероглифическую письменность в слоговое или узелковое письмо.

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

Ричард Хемминг, наверное, раньше других понял, что если избыточность не устранять, а разумно организовать, то ее можно использовать в системах связи для обнаружения ошибок и автоматического их исправления в кодовых словах передаваемого текста. Он понял, что все 128 семиразрядных двоичных слов могут использоваться для обнаружения ошибок в кодовых словах, которые образуют код — подмножество из 16 семиразрядных двоичных слов. Это была гениальная догадка.

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

Построение (7, 4)-кода Хемминга

Вернемся к Хеммингу. Слова (7, 4)-кода образованы из 7 разрядов С j = , j = 0(1)15, 4-информационные и 3-проверочные символа, т.е. по существу избыточные, так как они не несут информации сообщения. Эти три проверочных разряда удалось представить линейными функциями 4-х информационных символов в каждом слове, что и обеспечило обнаружение факта ошибки и ее места в словах, чтобы внести исправление. А (7, 4)-код получил новое прилагательное и стал линейным блоковым двоичным.

Линейные функциональные зависимости (правила (*)) вычислений значений символов
имеют следующий вид:

Исправление ошибки стало очень простой операцией — в ошибочном разряде определялся символ (ноль или единица) и заменялся другим противоположным 0 на 1 или 1 на 0.
Сколько же различных слов образуют код? Ответ на этот вопрос для (7, 4)-кода получается очень просто. Раз имеется лишь 4 информационных разряда, а их разнообразие при заполнении символами имеет = 16 вариантов, то других возможностей просто нет, т. е. код состоящий всего из 16 слов, обеспечивает представление этими 16-ю словами всю письменность всего языка.

Информационные части этих 16 слов получают нумерованный вид №
():

0=0000; 4= 0100; 8=1000; 12=1100;
1=0001; 5= 0101; 9=1001; 13=1101;
2=0010; 6= 0110; 10=1010; 14=1110;
3=0011; 7= 0111; 11=1011; 15=1111.

Каждому из этих 4-разрядных слов необходимо вычислить и добавить справа по 3 проверочных разряда, которые вычисляются по правилам (*). Например, для информационного слова №6 равного 0110 имеем и вычисления проверочных символов дают для этого слова такой результат:

Шестое кодовое слово при этом приобретает вид: Таким же образом необходимо вычислить проверочные символы для всех 16-и кодовых слов. Подготовим для слов кода 16-строчную таблицу К и последовательно будем заполнять ее клетки (читателю рекомендую проделать это с карандашом в руках).

Таблица К – кодовые слова Сj, j = 0(1)15, (7, 4) – кода Хемминга

Описание таблицы: 16 строк — кодовые слова; 10 колонок: порядковый номер, десятичное представление кодового слова, 4 информационных символа, 3 проверочных символа, W-вес кодового слова равен числу ненулевых разрядов (≠ 0). Заливкой выделены 4 кодовых слова-строки — это базис векторного подпространства. Собственно, на этом все — код построен.

Таким образом, в таблице получены все слова (7, 4) — кода Хемминга. Как видите это было не очень сложно. Далее речь пойдет о том, какие идеи привели Хемминга к такому построению кода. Мы все знакомы с кодом Морзе, с флотским семафорным алфавитом и др. системами построенными на разных эвристических принципах, но здесь в (7, 4)-коде используются впервые строгие математические принципы и методы. Рассказ будет как раз о них.

Математические основы кода. Высшая алгебра

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

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

Создатели кодов, долго не могли додуматься до кода, обнаруживающего и исправляющего две ошибки. Идеи, использованные Хеммингом, там не срабатывали. Пришлось искать, и нашлись новые идеи. Очень интересно! Захватывает. Для поиска новых идей потребовалось около 10 лет и только после этого произошел прорыв. Коды, обнаруживающие произвольное число ошибок, были получены сравнительно быстро.

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

Во-первых, они являются подпространством со всеми вытекающими отсюда свойствами и особенностями, во-вторых, кодовые слова являются подгруппой большой группы порядка 128, даже более того, аддитивной подгруппой конечного расширенного поля Галуа GF() степени расширения n = 7 и характеристики 2. Эта большая подгруппа раскладывается в смежные классы по меньшей подгруппе, что хорошо иллюстрируется следующей таблицей Г. Таблица разделена на две части: верхняя и нижняя, но читать следует как одну длинную. Каждый смежный класс (строка таблицы) — элемент факторгруппы по эквивалентности составляющих.

Таблица Г – Разложение аддитивной группы поля Галуа GF () в смежные классы (строки таблицы Г) по подгруппе 16 порядка.

Столбцы таблицы – это сферы радиуса 1. Левый столбец (повторяется) – синдром слова (7, 4)-кода Хемминга, следующий столбец — лидеры смежного класса. Раскроем двоичное представление одного из элементов (25-го выделен заливкой) факторгруппы и его десятичное представление:

Техника получение строк таблицы Г. Элемент из столбца лидеров класса суммируется с каждым элементом из заголовка столбца таблицы Г (суммирование выполняется для строки лидера в двоичном виде по mod2). Поскольку все лидеры классов имеют вес W=1, то все суммы отличаются от слова в заголовке столбца только в одной позиции (одной и той же для всей строки, но разных для столбца). Таблица Г имеет замечательную геометрическую интерпретацию. Все 16 кодовых слов представляются центрами сфер в 7-мерном векторном пространстве. Все слова в столбце от верхнего слова отличаются в одной позиции, т. е. лежат на поверхности сферы с радиусом r =1.

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

Здесь возникает требование к словам кода и к коду в целом: расстояние между любыми двумя кодовыми словами должно быть не менее трех, т. е. разность для пары кодовых слов, например, Сi = 85==1010101; Сj = 25== 0011001 должна быть не менее 3; 85 — 25 = 1010101 — 0011001 =1001100 = 76, вес слова-разности W(76) = 3. (табл. Д заменяет вычисления разностей и сумм). Здесь под расстоянием между двоичными словами-векторами понимается количество не совпадающих позиций в двух словах. Это расстояние Хемминга, которое стало повсеместно использоваться в теории, и на практике, так как удовлетворяет всем аксиомам расстояния.

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

Таблица Д — Сумма элементов группы (кодовых слов), используемой для построения кода Хемминга

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

Применение кода. Кодер

Пример 1. Необходимо передать слово «цифра» в ЕЯ. Входим в таблицу ASCII-кодов, буквам соответствуют: ц –11110110, и –11101000, ф – 11110100, р – 11110000, а – 11100000 октеты. Или иначе в ASCII — кодах слово «цифра» = 1111 0110 1110 1000 1111 0100 1111 0000 1110 0000

с разбивкой на тетрады (по 4 разряда). Таким образом, кодирование слова «цифра» ЕЯ требует 10 кодовых слов (7, 4)-кода Хемминга. Тетрады представляют информационные разряды слов сообщения. Эти информационные слова (тетрады) преобразуются в слова кода (по 7 разрядов) перед отправкой в канал сети связи. Выполняется это путем векторно-матричного умножения: информационного слова на порождающую матрицу. Плата за удобства получается весьма дорого и длинно, но все работает автоматически и главное — сообщение защищается от ошибок.
Порождающая матрица (7, 4)-кода Хемминга или генератор слов кода получается выписыванием базисных векторов кода и объединением их в матрицу. Это следует из теоремы линейной алгебры: любой вектор пространства (подпространства) является линейной комбинацией базисных векторов, т.е. линейно независимых в этом пространстве. Это как раз и требуется — порождать любые векторы (7-разрядные кодовые слова) из информационных 4-разрядных.

Порождающая матрица (7, 4, 3)-кода Хемминга или генератор слов кода имеет вид:

Справа указаны десятичные представления кодовых слов Базиса подпространства и их порядковые номера в таблице К
№ i строки матрицы — это слова кода, являющиеся базисом векторного подпространства.

Информационные слова сообщения имеют вид:

Это половины символа (ц). Для (7, 4)-кода, определенного ранее, требуется найти кодовые слова, соответствующее информационному слову-сообщению (ц) из 8-и символов в виде:

Чтобы превратить эту букву–сообщение (ц) в кодовые слова u, каждую половинку буквы-сообщения i умножают на порождающую матрицу G[k, n] кода (матрица для таблицы К):

Получили два кодовых слова с порядковыми номерами 15 и 6.

Покажем детальное формирование нижнего результата №6 – кодового слова (умножение строки информационного слова на столбцы порождающей матрицы); суммирование по (mod2)

∙ = 0∙1 +1∙0 + 1∙0 + 0∙0 = 0(mod2);
∙ = 0∙0 +1∙1 + 1∙0 + 0∙0 = 1(mod2);
∙ = 0∙0 +1∙0 + 1∙1 + 0∙0 = 1(mod2);
∙ = 0∙0 +1∙0 + 1∙0 + 0∙1 = 0(mod2);
∙ = 0∙0 +1∙1 + 1∙1 + 0∙1 = 0(mod2);
∙ = 0∙1 +1∙0 + 1∙1 + 0∙1 = 1(mod2);
∙ = 0∙1 +1∙1 + 1∙0 + 0∙1 = 1(mod2).

В результате перемножения получили 15 и 6 слова таблицы К кода.

Применение кода. Декодер

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

Основной задачей декодера является проверка того, является ли полученное слово (7 разрядов) тем, которое было отправлено на передающей стороне, не содержит ли слово ошибок. Для решения этой задачи для каждого полученного слова декодером путем умножения его на проверочную матрицу Н[n-k, n] вычисляется короткий вектор-синдром S (3 разряда).

Рассматриваемый код является систематическим, т. е. символы информационного слова размещаются подряд в старших разрядах кодового слова. Восстановление информационных слов выполняется простым отбрасыванием младших (проверочных) разрядов, число которых известно. Далее используется таблица ASCII-кодов в обратном порядке: входом являются информационные двоичные последовательности, а выходом – буквы алфавита естественного языка. Итак, (7, 4)-код систематический, групповой, линейный, блочный, двоичный.

Основу декодера образует проверочная матрица Н[n-k, n], которая содержит число строк, равное числу проверочных символов, а столбцами все возможные, кроме нулевого, столбцы из трех символов . Проверочная матрица строится из слов таблицы К, они выбираются так, чтобы быть ортогональными к кодирующей матрице, т.е. их произведение — нулевая матрица. Проверочная матрица получает следующий вид в операциях умножения она транспонируется. Для конкретного примера проверочная матрица Н[n-k, n] приведена ниже:

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

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

Пример 3. Обнаружение одной ошибки в слове, полученном на приемном конце канала (таблица К).

А) Пусть требуется передать 7 – е кодовое слово, т.е.

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

Выполним такое умножение для наших исходных (7-го вектора с ошибкой) данных.

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

Вот собственно и все, именно так устроен и работает классический (7, 4)-код Хемминга.

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

Заключение

В работе рассмотрены основные положения и задачи информационной безопасности, названы теории, призванные решать эти задачи.

Задача защиты информационного взаимодействия субъектов и объектов от ошибок среды и от воздействий нарушителя относится к кодологии.

Рассмотрен в деталях (7, 4)-код Хемминга, положивший начало нового направлению в теории кодирования — синтеза корректирующих кодов.

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

Источник