Напечатать документ Послать нам письмо Сохранить документ Форумы сайта Вернуться к предыдущей
АКАДЕМИЯ ТРИНИТАРИЗМА На главную страницу
Институт Золотого Сечения - Под знаком "Золотого Сечения"

А.П. Стахов
Системы счисления с иррациональными основаниями как теоретическая основа специализированной информатики и цифровой метрологии для критически-важных приложений

Oб авторе

Часть I. Критически-важные приложения и парадокс кода Хемминга

1. Введение

В последние недели на сайте АТ развернулась бурная дискуссия, посвященная «компьютерам Фибоначчи» [1 - 4]. Авторами этих статей являются:

1. Доктор экономических наук профессор И.С. Ткаченко, который вместе с сыном М.И. Ткаченко предложил оригинальный вариант развития «арифметики Фибоначчи», основанной на использовании так называемой «гиперболической тригонометрии Фибоначчи» [5]. У меня самое высокое мнение о творческом потенциале Ивана Семеновича Ткаченко, с которым мне пришлось работать в Винницком техническом университете. Хотя он и не является специалистом в области «компьютеров Фибоначчи», но его статья [1] свидетельствует об оригинальности его научного мышления.

2. Доктор технических наук С.Л. Василенко, автор статьи [2]. Судя по его личной странице в АТ [6], С.Л. Василенко 30 лет проработал на Харьковском водопроводе и дослужился до должности главного гидролога. Кандидатская диссертация «Статистическое моделирование качества воды в водотоках» (1998), докторская «Экологическая безопасность систем водоснабжения городов: методология изучения и управления» (2007). Сфера научных интересов: экология и водные ресурсы, математическое моделирование, управляющие, информационные и водохозяйственные системы, питьевое водоснабжение. Наверное, С.Л. Василенко – неплохой специалист в области водоснабжения, но какое отношение это имеет к золотому сечению, числам Фибоначчи, тем более, к «компьютерам Фибоначчи»?

По моему мнению, у С.Л. Василенко нет никаких оригинальных идей в области ЗС. Все его работы можно назвать «размышлизмами» (по меткому выражению самого Василенко), которые полностью соответствуют украинской пословице «чув звін та не знає, де він». Когда читаешь «размышлизмы» С.Л. Василенко, на ум сразу же приходит знаментитое стихотворение Пушкина «Сапожник».

3. Доктор технических наук в области информатики, профессор А.А. Борисенко, автор статьи [3]. Его можно назвать настоящим профессионалом в области «компьютеров Фибоначчи». Ему принадлежат оригинальные идеи по реализации типовых узлов «компьютера Фибоначи», а его аспиранты пишут и защищают кандидатские диссертации по тематике «Компьютеры Фибоначчи». Его статья [3] содержит глубокий критический анализ статьи С.Л. Василенко [2] и моей статьи [4], написанной в ответ на статью [2]. Хотя я не совсем согласен с некоторыми утверждениями А.А. Борисенко, но благодарю его за добросовестный и благожелательный анализ проблемы «компьютеры Фибоначчи».

В начале этого года я написал новую книгу «Numeral Systems with Irrational Bases for Mission-Critical Applications”, которая принята для публикации в “World Scientific» (http://www.worldscientific.com/worldscibooks/10.1142/10671)

Настоящая статья написана по мотивам этой книги и ставит задачу ознакомить русскоязычных читателей с ее содержанием. Статья состоит из двух частей:


Часть I. Критически-важные приложения и парадокс кода Хемминга

Часть II. «Троянский конь» двоичной системы и новые научные идеи в технической реализации информационных систем Фибоначчи для критически-важных приложений


Вашему вниманию предлагается Часть I настоящей статьи.


2. Проблема борьбы с помехами

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

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

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


3. Критически-важные приложения (mission-critical applications)

В настоящее время информатика переходит на новый этап своего развития, который связан с так назывемыми «критически-важными приложениями» (mission-critical applications).

Статья [8] посвящена определению понятия «mission-critical applications»:

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

Критически важная система (Mission-Critical System) - это система, отказ которой может привести к отказу от какой-либо целенаправленной деятельности. Критически-важное оборудование (Mission-essential equipment) и критически-важное приложение (mission critical application) также известны под названием «критически важных систем» (mission-critical system). Примерами критически важных систем являются: система онлайн-банкинга, системы управления и контроля на железнодорожном / воздушном транспорте, системы электроснабжения и многие другие компьютерные системы, которые могут серьезно повлиять на бизнес и общество, если они будут подвержены ошибкам. Хорошим примером критически-важной системы является навигационная система для космического корабля».

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

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


4. Типовая модель ошибок, используемая в последовательных информационных системах

4.1. Два типа информационных систем

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

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


4.2. Типовая модель ошибок

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

Модель так называемого «симметричного канала» как простейшая вероятностная модель ошибок широко используется в традиционных последовательных системах передачи данных. Детальный анализ этой модели приведен в книге «Борьба с помехами» [7], написанной выдающимся советским ученым академиком Харкевичем, который много лет возглавлял Институт проблем передачи информации Академии наук СССР.

Ограничимся вербальным описаниеем такой модели в книге Харкевича [7]:

«Коды для исправления ошибок были созданы первоначально для обнаружения и исправления независимых ошибок. В этом случае важную роль играет понятие минимального кодового расстояния ... В случае независимых ошибок вероятность ошибки уменьшается с увеличением ее кратности».

Эта цитата содержит три важные идеи, которые положены в основу существующей теории корректирующих кодов:

  1. Корректирующие коды первоначально были созданы для обнаружения и исправления независимых ошибок, возникающих в последовательных системах передачи данных.
  2. Идея независимых ошибок сыграла ключевую роль при введении понятия «минимального кодового расстояния» (или расстояния Хэмминга), которое является одним из важнейших понятий теории корректирующих кодов.
  3. В случае независимых ошибок вероятность ошибок уменьшается с увеличением их кратности, что легко показать математически.

Продолжая свои рассуждения, Харкевич приходит к следующему заключению [7], которое можно рассматривать как основную цель теории корректирующих кодов:

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

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

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

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


5. Анализ ошибок в «вычислительных каналах»

5.1. Предположения У. Коца

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

Известный американский эксперт в области кодирования У.Коц в статье [13] отмечает, что попытка использовать существующие корректирующие коды для цифровых систем с параллельным представлением данных может оказаться неэффективной из-за следующих особенностей «вычислительных каналов»:

«1) критерий эффективности может отличаться от соответствующего критерия для традиционного канала связи;

2) наиболее вероятные ошибки могут не соответствовать наиболее вероятным ошибкам в обычном канале связи;

3) необходимо принимать во внимание возможность ошибок вследствие неисправностей в самой декодирующей логике (корректоре);

4) коды должны по возможности обеспечивать выполнение арифметических и других операций» ([13], с.179).

Опубликованные в работе [14] экспериментальные данные об ошибках в типовых узлах «вычислительных каналов» (счетчиках, регистрах, сумматорах) достаточно убедительно подтверждают соображения Коца и свидетельствуют о том, что характер реальных ошибок в «вычислительных каналах» не соответствуют предположениям, принятым в модели «симметричного канала».

Анализ полученных в работе [14] экспериментальных данных привел к следующим любопытным результатам:

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

2) Счетчик с непосредственными связями и накапливающий сумматор можно считать устройствами с резко выраженным асимметричным характером ошибок. Так, вероятность ложного увеличения и уменьшения числа в счетчике соответственно равны 0,96 и 0,04, для сумматоров эти вероятности соответственно равны 0,8 и 0,2.

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


5.2. “Row hammer” effect - это новое явление в области электронной памяти. В статье [15] сущность этого эффекта объясняется следующим образом:

Row hammer» … является непреднамеренным побочным эффектом в динамической памяти с произвольным доступом (DRAM), которая заставляет строки памяти переносить свои заряды и взаимодействовать между собой электрически, возможно изменяя содержимое соседних строк памяти, которые не были адресованы в исходном доступе к памяти. Этот обход изоляции между строками памяти DRAM обусловлен высокой плотностью ячеек памяти в современной DRAM ... »

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

Хотя статьи [13,14] опубликованы в прошлом веке, однако это тот случай, когда результаты этих исследований не только не стареют, а становятся еще более актуальными в настоящее время, особенно в связи возникновением эффектов, подобных row hammer” эффекту [15].


6. Парадокс кодов Хемминга и Хсяо

Ущербность традиционного подхода к теории корректирующих кодов, вытекающего из модели «симметричного канала» [7], можно показать на примере кодов Хемминга и Хсяо [9-11], широко используемых для обнаружения и исправления ошибок в информационных системах с представлением данных в параллельной форме.

Как известно, коды Хемминга [9] и Хсяо [9-11] широко используются для исправления однобитных ошибок, возникающих в информационных системах с параллельным представлением данных (например, в электронной памяти).

Так называемый немодифицированный код Хэмминга [9] позволяет исправить однобитную ошибку в кодовом слове. В случае 2-битной (или двойной) ошибки корректор не может ее обнаружить и «тупо» воспринимает кодовое слово с двойной ошибкой как слово с однобитной ошибкой и сообщает об успешной коррекции якобы однобитной ошибки в кодовом слове. Этот случай называется «ложной коррекцией». Для обнаружения двойной ошибки в кодовом слове используется модифицированный код Хемминга типа SEC-DED, что означает исправление однобитной ошибки (SEC) и обнаружение двойной ошибки (DED). Модифицированный код Хемминга отличается от немодифицированного добавлением еще одного бита проверки, который является общим битом четности всего кодового слова Хемминга. Однако, в случае ошибок кратности больше 2 (особенно нечетной кратности 3,5,7,...) существует вероятность возникновения «ложной коррекции».

Модифицированные Хсяо коды [10,11] аналогичны модифицированному коду Хемминга, но используют несколько другую математическую основу.

Возникает вопрос: как действуют модифицированные коды Хемминга и Хсяо, когда в кодовом слове возникают ошибки большой нечетной кратности (3,5,7,9, ...)? Такие многобитовые ошибки нечетной кратности (3,5,7,9, ...) «тупо» воспринимаются корректорами кода Хемминга и Хсяо как однобитовые ошибки и корректоры начинают корректировать ошибочные кодовые слова, добавляя к ним новые ошибочные биты.


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


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

Модифицированные коды Хемминга и Хсяо различаются вероятностью обнаружения 3-битных (тройных) и 4-битных (четырехкратных) ошибок (а также других ошибок большой кратности). Сравнение этих кодов для случая 3-битных ошибок представлено в таблице 1 (таблица взята из [11]).

Таблица 1. Вероятность «ложного исправления» и обнаружения ошибок для кодов Хемминга и Сяо для 64-битного информационного слова


Эта таблица подтверждает, что модифицированные коды Хэмминга и Хсяо имеют очень высокий процент «ложных исправлений» 3-битных ошибок, что НЕДОПУСТИМО для критически важных приложений. К сожалению, в Таблице 1 не приводятся данные о вероятности «ложной коррекции» нечетных ошибок более высокой кратности (5,7,9, ...); однако мы не можем игнорировать и эти ошибки в критически важных системах.

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


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

(Продолжение следует)


Литература

[1] И.С. Ткаченко, М.И. Ткаченко, Функции Фибоначчи, операции троичной логики, автоматы 3-го рода Л.Ф. Мараховского как основа построения сумматора Фибоначчи-компьютера // «Академия Тринитаризма», М., Эл № 77-6567, публ.23632, 14.08.2017

[2] С.Л. Василенко, О «компьютерах Фибоначчи» // «Академия Тринитаризма», М., Эл № 77-6567, публ.23653, 20.08.2017

[3] А.А. Борисенко, Реплика «Множьте сущности» (к дискуссии о компьютерах Фибоначчи) // «Академия Тринитаризма», М., Эл № 77-6567, публ.23680, 30.08.2017

[4] А.П. Стахов, Оптимистичный взгляд на «Компьютеры Фибоначчи» // «Академия Тринитаризма», М., Эл № 77-6567, публ.23656, 22.08.2017

[5] Стахов А.П., Ткаченко И.С. Гиперболическая тригонометрия Фибоначчи. Доклады Академии наук УССР, том 208, № 7, 1993 г.

[6] Василенко С.Л. АТ, личная страница http://www.trinitas.ru/rus/doc/avtr/01/0738-00.htm

[7] Харкевич, A.A. Борьба с помехами. Москва: Физматгиз, 1963.

[8] Mission critical. From Wikipedia, the free encyclopaedia https://en.wikipedia.org/wiki/Mission_critical

[9] Hamming code. From Wikipedia, the free encyclopedia https://en.wikipedia.org/wiki/Hamming_code

[10] Hsiao M.Y. (1970) A class of optimal minimum odd-weight-column SEC-DED codes. IBM J. Res. Develop. Vol. 14.

[11] Петров К.А. Исследование характеристик помехоустойчивых кодов, используемых в субмикронных статических ОЗУ http://gigabaza.ru/doc/194118.html

[12] Стахов А.П. Введение в алгоритмическую теорию измерения. Москва: Советское Радио, 1977.

[13] Коц У. Коды с исправлением ошибок и их реализация в цифровых системах. В кн. «Методы введения избыточности для вычислительных систем. Москва: Советское Радио, 1966.

[14] Обнаружение и исправление ошибок в дискретных устройствах. Под ред. В.С. Тостякова. Москва, Советское Радио, 1972. Авторы: В.С. Толстяков, В.Н. Номоконов, М.Г. Карповский и др.

[15] Row hammer. From Wikipedia, the free encyclopaedia https://en.wikipedia.org/wiki/Row_hammer



А.П. Стахов, Системы счисления с иррациональными основаниями как теоретическая основа специализированной информатики и цифровой метрологии для критически-важных приложений // «Академия Тринитаризма», М., Эл № 77-6567, публ.23686, 01.09.2017

[Обсуждение на форуме «Публицистика»]

В начало документа

© Академия Тринитаризма
info@trinitas.ru