УДК 621.3.049.771.14
	
С.В. Гаврилов [д.т.н., заведующий отделом, Институт проблем проектирования в микроэлектронике РАН], 
С.И. Гуров [доцент, Московский государственный университет имени М. В. Ломоносова],
Т.Д. Жукова [инженер-исследователь, Институт проблем проектирования в микроэлектронике РАН],
Д.И. Рыжова [м.н.с., Институт проблем проектирования в микроэлектронике РАН]

Применение теории кодирования для повышения помехозащищённости комбинационных схем

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

Gavrilov S.V.
Gurov S.I.
Zhukova T.D.
Ryzhova D.I.

Application of coding theory to improve the noise immunity of combinational circuits
Abstract – The work is devoted to solving problems of design automation to improve the noise immunity of combinational integrated circuits at the synthesis and logical design. The different methods of error-correcting coding for improving noise immunity of combinational integrated circuits are analyzed. The coding methods with a selection of duplicate circuit outputs commutation based on the logical correlations between the circuit outputs are implemented. One of the significant difference of the noise immunity of combinational circuits, in comparison with coding in data networks, is an additional degree of freedom associated with the implementation of the coding scheme. The application of effective optimization methods reduces the size of coding circuit by selection of the commutation order, compared to the majority approach.
Key words – combinational circuits, design, noise tolerance, CAD.

Введение
Среди известных подходов к проектированию помехоустойчивых интегральных схем (ИС) широко распространено дублирование с выбором результата по мажоритарному принципу [1]. Однако в последнее время всё больший интерес вызывают попытки применения для решения данной задачи методов помехоустойчивого кодирования, которые аналогичны по своей сути подходам к защите от помех потоков информации при ее передаче по линиям связи [2].
Традиционным методом повышения отказоустойчивости при информационных сбоях в каналах связи является помехоустойчивое кодирование. Для парирования информационных сбоев, возникших в результате сбоев аппаратных, возможно использование следующих подходов [3]:
1)	Аппаратное резервирование с дальнейшим применением мажорирования – процедуры коррекции искажённой в результате сбоя информации путём сравнения результатов, полученных параллельным путём, и выдача на выход наиболее совпадающих результатов.
2)	Информационное резервирование с применением результатов теории кодов, исправляющих/обнаруживающих ошибки.
Поскольку информационные сбои ИС обычно возникают в результате воздействия заряженных частиц или иных помех, в данном случае как аналоги понятий «отказоустойчивость» и «надёжность» используют термины «помехоустойчивость» и «помехозащищённость» (ИС) соответственно. 
Информационные сбои (кратковременные самовосстанавливающиеся отказы) в ИС появляются результате воздействия на схему различных видов помех: радиационных, скачков напряжений питания, деградаций сигналов во времени и др. Исследования показывают, что вероятность ошибки от указанных причин может варьироваться в очень широких пределах: от менее, чем  до  для больших и очень маленьких схем соответственно [18]. В статье как аналоги понятий «отказоустойчивость» и «надёжность» используют термины «помехоустойчивость» и «помехозащищённость» ИС соответственно. 
Одним из существенных отличий задачи кодирования комбинационных схем, по сравнению с кодированием в сетях передачи данных, является дополнительная степень свободы, связанная с реализацией схемы кодирования. 
Дальнейшее содержание работы следующее: в части 1 представлен анализ существующих подходов к кодированию информации для решения задачи повышения помехозащищённости комбинационных схем, в части 2 приведено описание применения методов помехоустойчивого кодирования для повышения помехозащищённости комбинационных интегральных схем, а также рассмотрены методы построения оптимальных схем коммутирования выходов схемы кодирования на основе анализа вероятностей распространения парных корреляций в схеме.

1.	Анализ существующих методов блокового кодирования
1.1	Общие понятия
Опишем кратко основные положения теории кодов, исправляющих ошибки. Помехоустойчивость кодирования достигается введением избыточности в код. Наиболее простая модель возникновение ошибок ‑ двоичный симметричный канал со случайным некоррелированным информационным потоком, в котором некоторые биты случайно, равновероятно и независимо друг от друга могут оказаться инвертированными, а добавления или стирания бит отсутствуют. При этом могут ставиться задачи автоматического обнаружения и/или исправления ошибок. 
Одним из один из возможных подходов к решению проблемы является разбиение потока информации на сообщения – непересекающиеся блоки фиксированной длины . Каждый блок можно кодировать независимо от других – блоковое кодирование или в зависимости от предыдущих – свёрточное кодирование [4-6]. В результате вместо сообщений передают кодовые слова длины  каждое. Естественно требовать построения кода минимальной длины, позволяющего восстановить сообщение, содержащее не более данного количества  ошибок.
Далее будем рассматривать исключительно блоковое кодирование.
Если кодовое слово длины  содержит в себе  бит исходного сообщения (информационные биты) и дополнительно ещё  проверочных бит, то говорят о разделимом блоковом кодировании. В неразделимых кодах выделить информационные и проверочные биты невозможно. Величину  называют избыточностью кода. Увеличение  ведёт, вообще говоря, к увеличению кодового расстояния  и, следовательно, к увеличению количества ошибок, которые может исправить код. Минимальное расстояние  между словами кода называется кодовым расстоянием. Очевидно у кода, исправляющего  ошибок . Разделимый блоковый код описывают тройкой параметров  или парой .
Определение кодового расстояния  произвольного кода – сложная задача. Поэтому при создании помехоустойчивых кодов на первый план выходит проблема построения кодов с заданным кодовым расстоянием. Она решается при использовании БЧХ-кодов [7]. На сегодняшний день БЧХ-коды с практически значимыми параметрами уже построены. 
Блоковое кодирование есть взаимно-однозначное отображение множества сообщений (всех векторов ) во множество кодовых слов (некоторых векторов ). Оно всегда может быть осуществлено с использованием таблицы размера . Однако такое табличное кодирование весьма неэффективно: значения  и  на практике могут достигать десятков и сотен тысяч. Известны две конструкции т.н. совершенных кодов, плотно заполняющих шарами радиуса  с центрами в кодовых словах весь куб : это коды Хемминга  и код Голея . 
При передаче по каналу с шумом кодовое слово  превращается в принятое слово , где  – вектор ошибок. Код Хэмминга может быть построён так, что проверочные биты будут содержать номер (единственной) искажённой позиции принятого слова.
Декодирование состоит в определении сообщения по кодовому слову. Декодирование кодов обычно значительно сложнее кодирования. (исключением являются т. н. экспандерные коды с линейным декодированием, для которых неизвестны субквадратичные алгоритмы кодирования). Декодирование -кода основано на разбиении единичного куба  на  областей, содержащих шары радиуса  с центрами в кодовых словах. Тогда восстановление сообщения переданного сообщения  состоит в (1) определении слова , ближайшего к полученному  и (2) удалению из  проверочных бит. В общем случае эти операции потребуют использования таблиц экспоненциального по  размера. Таким образом декодирование блокового -кода общего вида – весьма ресурсоёмкий процесс и поэтому его использование таких кодов возможно лишь при небольших значениях  и . Однако, приняв ряд дополнительных ограничений на множество кодовых слов, можно перейти от экспоненциальных требований по памяти и по сложности алгоритмов кодирования/декодирования к линейным по  и . Эти ограничения приводят к использованию блоковых кодов специального вида: групповых, а из групповых – циклических.
1.2	Групповые (линейные) коды
Бóльшая часть теории блокового кодирования построена на линейных кодах, образующих векторное подпространство координатного пространства . В линейных кодах сумма по  любых кодовых слов – также кодовое слово. Линейные коды позволяют реализовывать эффективные алгоритмы кодирования/декодирования и в двоичном случае их называют групповыми, т. к. они образуют группу относительно операции «сумма по ». Линейные -коды могут быть заданы матрицами ‑ порождающей  или проверочной . Для них выполняются соотношения ,  для любого кодового слова , а невыполнение последнего равенства свидетельствует о наличии ошибки.
На практике удобно использовать систематическое кодирование [8], при котором биты сообщения копируются в фиксированные позиции кодового слова, а затем вычисляются остальные проверочные биты. Такая возможность основана на том, что порождающая и проверочная матрицы определены с точностью до эквивалентных преобразований столбцов и строк соответственно, что эквивалентно переходу к другому базису пространствах кодовых слов и ортогонального ему. Фиксирование позиций информационных бит задаёт порождающую и проверочную матрицы однозначно. При этом второй этап декодирования (удаление проверочных бит) становится тривиальным.
Декодирование групповых кодов проводят с использованием синдромов – векторов . Вычисление вектора ошибок  сводится к решению СЛАУ , которое ищут в виде суммы частного решения данной и общего решения соответствующей однородной системы. После нахождения решения все возможные кодовые слова  входного вектора дадут  вариантов вектора ошибок, среди которых выбирают с наименьшим хэмминговым весом. 
Таким образом, кодирование групповыми кодами осуществляется умножением вектора сообщения на порождающую матрицу. Декодирование также значительно упрощается по сравнению с общим случаем: используются легко вычисляемые синдромы при элементарном этапе удаления проверочных бит в случае систематического кодирования. Однако алгоритм декодирования линейного кода в общем случае остаётся экспоненциально трудоёмким и по памяти, и по числу операций. 
Для линейных кодов, рассчитанных на исправление многократных ошибок, часто более простыми оказываются декодирующие устройства, построенные по мажоритарному принципу. Это метод декодирования называют также принципом голосования или способом декодирования по большинству проверок и тоже базируется на системе проверочных равенств. 
1.3	Циклические коды
Циклические коды – подкласс линейных [9]. Код называется циклическим (сдвиговым) (Cyclic Redundancy Code, CRC), если он инвариантен относительно циклических сдвигов.
В теории конечных полей (полей Галуа) показывается, что идеал неприводимого делителя бинома  образует циклическое подпространство в факторкольце многочленов  (а циклический сдвиг в нём осуществляется умножением на ). Поэтому для построения циклического кода выбирают некоторый неприводимый делитель  бинома  и в качестве кодовых слов рассматривают порождённый им идеал  – все многочлены, делящиеся на  без остатка. При удачном выборе  коэффициенты многочленов из данного идеала будут давать код с малой избыточностью при большом кодовом расстоянии. Однако известны только несколько конструкций циклических кодов с хорошими параметрами, а в общем случае определение кодового расстояния циклического кода чрезвычайно сложно.
При использовании циклических кодов удобно пользоваться представлением векторов сообщения  и кодового слова  в виде полиномов : например, .
Различают систематическое и несистематическое кодирование циклическими кодами, которое приводит к разделимому и неразделимому кодированию. Несистематическое осуществляется путём умножения кодируемого вектора на : , а систематическое ‑ дописыванием к кодируемому слову остатка  от деления  на  ‑ в этом случае полином  содержит коэффициенты полинома  в  крайних правых позициях (т. е. при старших степенях ).
Синдромом  принятого полинома , закодированного циклическим -кодом с порождающим полиномом , называют остаток от деления  на  (очевидно, это перефразировка в терминах полиномов синдрома для групповых кодов). Равенство  означает, что, то  – кодовое слово.
Декодирование циклического кода проходит по общей схеме декодирования линейного кода: вычисляется синдром  принятого слова , ищутся решения системы  для всех  возможных полиномов  степени , определяется полином ошибок как решение с минимальным числом ненулевых слагаемых и, наконец, восстанавливается переданное сообщение .
Циклические коды общего вида могут иметь произвольную длину , но, в отличие от линейных, его параметры  и  уже не произвольны. При использовании циклических кодов вместо матричных умножений и решения СЛАУ используются более простые операции умножения и деления с остатком полиномов, легко реализуемые на регистрах сдвига с обратными связями. Однако общий алгоритм декодирования по-прежнему имеет экспоненциальную сложность по . Существуют и альтернативные методы декодирования циклических кодов общего вида, но и они не имеют удовлетворительных характеристик.
Таким образом, обнаружение ошибок при помощи циклического кода обеспечивается тем, что в качестве разрешённых комбинаций выбираются такие, которые делятся без остатка на некоторый заранее выбранный порождающий полином. Если принятая комбинация содержит искажённые символы, то такое деление осуществляется с остатком и при этом формируется сигнал, свидетельствующий об ошибке. Большим преимуществом циклических кодов является простота построения кодирующих и декодирующих устройств, которые по своей структуре представляют регистры сдвига с обратными связями.
Важной особенностью комбинационных схем является то, что искажение информации, возникающее при их сбоях, вряд ли адекватно описывается в рамках традиционной описанной выше модели двоичного симметрического канала. Кажется, обоснованным предположение о том, что сбои ИС от описанных выше причин приводят к ошибкам константного (stick-at faults) типа, в результате чего типичной является ситуация либо полного отсутствия, либо наличия сразу достаточно большого количества ошибок. При этом соответствующие исследования неизвестны в литературе.

2.	Избыточное кодирование выходных данных цифровых комбинационных схем 
При использовании избыточного кодирования выходных данных комбинационных схем обычно штатную схему дополняют ещё одной, вычисляющей проверочные биты. Ясно, что в рассматриваемой задаче требования к качеству используемых кодов (избыточность при данном числе обнаруживаемых/исправляемых ошибок) не являются слишком жёсткими: для реальных схем с длинами входных и выходных векторов в несколько десятков бит разница между «хорошими» и «наилучшими» кодами несущественна и здесь на первый план выходят вопросы простоты практической реализации алгоритмов кодирования и декодирования. При этом имеющиеся технологические и схемные решения позволяют обеспечить существенно более высокий уровень помехозащищённости кодирующей схемы по сравнению с основной, что позволяет считать работу данной схемы безошибочной. Данные решения обосновываются тем, что длина вектора проверочных бит значительно короче вектора бит информационных. Это позволяет предполагать и существенно меньшую сложность кодирующей схемы по сравнению с основной и поэтому затраты на её защиту указанными средствами предполагаются оправданными. 
При построении избыточных кодов используют лишь часть возможных комбинаций бит в кодовых словах, которые называют разрешёнными (остальные комбинации запрещённые). Опишем кратко избыточные коды, применяемые и перспективные к применению для повышения помехозащищённости комбинационных схем. 
Примером нелинейного избыточного кода является код Бергера, у которого проверочные символы представляют двоичную запись числа единиц (или нулей) в последовательности информационных символов. Например, таким является разделимый систематический -код . Коды Бергера обнаруживают все одиночные ошибки и некоторую часть многократных. 
Также нелинейными являются остаточные -коды, имеющие  информационных и  контрольных разрядов. Последние содержат двоичное представление остатка от деления десятичного эквивалента числа, двоичное представление которого задают информационные разряды, на  [20]. Ясно, что при  имеем код с проверкой на чётность.
Для построения избыточных систематических линейных кодов с кодовым расстоянием  определяют позиции кода, в которые будут записываться информационные биты, а подматрица проверочных бит в проверочной матрице выбирается так, чтобы вес каждой её строки был не менее , а вес суммы по  двух любых строк ‑ не менее . 
Существует два основных методов декодирования рассматриваемых кодов: на основе кодов-спутников и проверочных соотношений [19]. Первый требует хранения больших объёмов данных, второй основан на вычислении синдромов. При этом легко вычисляются синдромы, позволяющие определить место одиночной ошибки, но для исправление ошибок большей кратности связано со значительными вычислительными трудностями. 
Самым простым избыточным кодом является код с (одной) проверкой на чётность, когда при кодировании каждого -битного сообщения добавляют один бит, содержащий 0 или 1 так, чтобы число единиц в коде было чётным. При таком кодировании обнаруживается искажение любого чётного числа символов. 
Код с простым повторением информационных символов — тривиальный избыточный код. Очевидно, применение его и его разновидностей (корреляционный, инверсный и т.д. коды) не даёт решения нашей задачи. 
Код Рида-Маллера ‑ линейный блочный -код с параметрами  ‑ порядок кода, количество информационных разрядов . Имеется простой способ построения порождающей матрицы, при котором код Рида-Маллера является систематическим и циклическим. Важным свойством рассматриваемых кодов является простота их декодирования, при котором исключается этап определения места ошибок и имеется возможность использования мажоритарного принципа декодирования [19]. 
Если число единиц во всех комбинациях кода будет постоянным, то такой код будет кодом с постоянным весом. Это блочные неразделимые коды. Наибольшее применение получили коды ; здесь первая цифра указывает на вес кода, вторая — на общее число символов в комбинации. Например, кодовыми словами кода  являются содержащие три единицы независимо от их места в комбинации, и таких слов 128. Обнаружение ошибки сводится к определению веса принятого слова и сравнению его с заданным. Код обнаруживает ошибки нечётной кратности и часть ошибок чётной кратности. Не обнаруживаются ошибки смещения, при которых несколько единиц превращается в нули и столько же нулей ‑ в единицы. 
Коды CRC (Cyclic Redundancy Check, циклическая избыточная проверка) являются систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования и декодирования с порождающим полиномом, изложенный выше. 
Линейные коды низкой плотности (LDPC, Low Density Parity-check Codes) или коды с малой плотностью проверок на чётность были предложены ещё в 1963 г., но потом были почти что забыты. В 1990-х годах обнаружилась их связь со специальным классом графов ‑ экспандерами, теория которых сейчас активно развивается. Данные коды описываются разреженными проверочными матрицами, что уменьшает число количество символов, входящих в проверочные соотношения. Существенной положительной стороной таких кодов является то, что не только кодирование, но и декодирование из выполняется достаточно быстро. 

3.	Применение помехоустойчивого кодирования для повышения помехозащищённости комбинационных интегральных схем 
3.1.	Предлагаемый метод повышения помехозащищённости
Для повышения помехозащищённости комбинационных схем был выбран метод с применением циклических кодов. Применение таких кодов позволяет не только обнаружить наличие ошибок в переданном сообщении, но и исправить определённое число ошибок. Количество ошибок, которое можно исправить определяется свойствами образующего многочлена [10-12]. Данный метод не приводит к неоправданной избыточности, а также обеспечивает возможность оптимального сочетания требований к минимизации аппаратных затрат и достижение требуемого уровня отказоустойчивости [13-14]. Схема предлагаемого подхода представлена на рисунке 1.
Для кодирования сообщений применяется операция умножения на образующий многочлен, при этом вектор исходного сообщения  представляется в виде многочлена , где  – длина сообщения. Для декодирования сообщения используется операция деления переданного сообщения на образующий многочлен. Остаток от деления принятого слова на образующий многочлен называется синдромом. Если ошибок в переданном сообщении нет, то синдром равен нулю. Вектор ошибок находится по вычисленному синдрому. 
Для кодирования выходного вектора комбинационной схемы  он представляется в виде многочлена , который умножается на образующий многочлен . Для декодирования возможно искажённого выходного вектора, представленного многочленом , последний делится на образующий многочлен c вычислением остатка от деления ‑ синдрома . В случае  по вычисленному синдрому находится вектор ошибок. 

Рисунок 1. Предлагаемый подход 
В задаче передачи сообщений для реализации операций умножения и деления многочленов используются сдвиговые регистры, так как сигнал передаётся в виде последовательности нулей и единиц. В случае комбинационных схем сигналы на выходы приходят параллельно, поэтому в данном случае необходимо использовать в качестве схем кодирования и декодирования логические схемы.
Принципиальное отличие задачи кодирования данных для передачи через канал связи от задачи повышения помехоустойчивости комбинационных схем состоит в следующем. Так как в задаче повышения помехоустойчивости сама комбинационная схема подвержена ошибкам, схема кодирования реализуется за счёт дублирования исходной схемы с последующей оптимизацией совместно со схемой кодирования. Для синтеза схемы кодирования используется операция умножения многочлена выходного сообщения комбинационной схемы  на образующий многочлен , где – степень образующего многочлена.
Ключевая проблема задачи передачи сообщений ‑ минимизация площади или размера схем кодирования и декодирования. Одним из путей оптимизации схемы является построение логических функций на основе применения аппарата бинарных диаграмм решений (BDD, Binary Decision Diagram), представляющих булеву функцию в виде направленного ациклического графа. Предлагаемое при этом использование синтеза булевых функций в полях Галуа на основе редуцированных диаграмм двоичных решений (ROBDD, Reduced Ordered Binary Decision Diagram), позволяет снять существующее в настоящее время ограничение на размерность проектируемых комбинационных схем (число входов и выходов). Использование предлагаемой методики обеспечивает управляемость и предсказуемость процесса проектирования схем при достижении оптимального сочетания заданных требований по отказоустойчивости и минимизации структурных затрат. Критерием оценки площади при применении BDD может служить количество узлов дерева. Оценку задержек можно рассчитать исходя из длины цепи от входа до выхода при предположении мультиплексорной реализации.
Проведённые исследования показали, что на качество результата в терминах занимаемой площади существенное влияние оказывает не только переупорядочивание входов, как в случае стандартной BDD, но и порядок коммутации выходов в схеме кодирования.
Для выбора оптимального варианта коммутации предлагается использовать оценочную функцию, вычисленную на основе расчёта взаимных корреляций между выходами [15]. Примеры синтеза схемы контроля на основе предложенного подхода приводились ранее в статьях [10-14]. Наибольший эффект от оптимизации схемы кодирования достигается при условии вхождения в одну формулу схемы кодирования выходов схемы, имеющих взаимные корреляции. Для всех выходов дублирующей схемы применяют предложенные методы анализа логических корреляций в цифровой схеме для получения весовых функций. На основе полученных весовых функций выбирается порядок коммутации выходов дублирующей схемы на основе анализа вероятностей распространения парных корреляций.
2.1.	Методы построения оптимальных схем коммутирования входов схемы кодирования с учётом логики работы основной схемы
За счёт учёта дискретных корреляций можно сократить размер схемы. Однако дискретные корреляции не описывают полную картину возможных корреляций сигналов в схеме. Для полного учёта парных корреляций в качестве альтернативы предлагается модифицировать аппарат анализа парных корреляций, который использовался при оптимизации мощности и анализе стрессовых состояний транзисторов [16].
Пусть каждый сигнал  в комбинационной схеме (либо первичный вход, либо выход любого вентиля) характеризуется с помощью величины , равной отношению времени нахождения сигнала в состоянии  к общему времени моделирования. Для описания корреляции между двумя сигналами введём коэффициент корреляции сигналов по аналогии с [17]:

, i, j =0, 1.			(1)
В целях устранения экспоненциальной сложности алгоритма можно воспользоваться предположением о том, что существенны только парные корреляции. Иначе говоря, будем пренебрегать корреляцией любых двух сигналов к третьему, и т.д. В этом случае вероятность сложного события может быть приближённо вычислена по формуле:

.		(2)

Поскольку

где ‑ вероятность события X при условии Y, то:

.
Следовательно, мы имеем следующие соотношения для четырёх коэффициентов :

,; j=0,1, i=0,1. 		(3)
Матрица системы (3) имеет ранг 3, поэтому, зная , можно вычислить три других коэффициента по формулам

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

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

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

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

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

.
Остальные коэффициенты  могут быть вычислены по формулам (4).
Формула учёта парных корреляций для выбора варианта коммутации может быть модифицирована следующим образом:

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

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

ЛИТЕРАТУРА
1.	Черкесов Г. Н. Надёжность аппаратно-программных комплексов // Учебное пособие. – СПб.: Питер, 2004. – 479 с.
2.	Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение // пер. с англ. В.Б. Афанасьева. – М.: Техносфера, 2006. – 320 с.
3.	Матвеевский В. Р. Надёжность технических систем // Учебное пособие, 2002. – 113 с
4.	Вернер М. Основы кодирования // Учебник для ВУЗов. – М.: Техносфера, 2004. – 288 с.
5.	Блейхут Р. Теория и практика кодов, контролирующих ошибки // М.: Книга по требованию, 2013. – 566 с.
6.	J.H. van Lint. Introduction to Coding Theory // Springer Science & Business Media, 2012.
7.	Poolakkaparambil M., Mathew J. BCH Code Based Multiple Bit Error Correction in Finite Field Multiplier Circuits // ISQED, 2011, pp. 1-6.
8.	MacWilliams F. J., Sloane N. J. A. The Theory of Error—Correcting Codes // North–Holland Publishing Company, 1977. 
9.	Касами Т., Токура Н., Ивадари Е. Теория кодирования // пер. с яп. А.В. Кузнецова. – М.: Мир, 1978. 
10.	Гаврилов С. В., Иванова Г. А., Рыжова Д. И., Соловьёв А. Н., Стемпковский А.Л. Методы синтеза помехозащищенных комбинационных блоков // Информационные технологии. 2015, Т. 21, №11. ‑ С. 821-826.
11.	Гаврилов С. В., Иванова Г. А., Рыжова Д. И., Стемпковский А. Л. Методы повышения надёжности комбинационных микроэлектронных схем на основе мультиинтервального анализа быстродействия // Системы высокой доступности. №4. 2015. ‑ С. 69-76.
12.	Соловьёв А. Н., Стемпковский А. Л. Методы повышения отказоустойчивости работы устройства управления микросистемы за счёт введения структурной избыточности // Информационные технологии. 2014, №10, С. 17-22.
13.	Гаврилов С. В., Иванова Г. А., Соловьёв А. Н., Стемпковский А. Л. Оптимизация схем кодирования на основе выбора варианта коммутаций с учётом логических корреляций между выходами комбинационной схемы // Известия ЮФУ. Технические науки. – 2015. №6 (167), C. 255-262.
14.	Гаврилов С. В., Иванова Г. А., Соловьёв А. Н., Щёлоков А. Н. Учёт логических корреляций между выходами комбинационной схемы при коммутации с входами схемы кодирования // Труды Международного конгресса по интеллектуальным системам и информационным технологиям – 2015, “IS&IT’15”. С. 192-197.
15.	Гаврилов С. В. Методы анализа логических корреляций для САПР цифровых КМОП СБИС. – М., Техносфера, 2011, 136 c.
16.	Стемпковский  А. Л., Глебов А. Л., Гаврилов С. В., Гудкова О. Н. Вероятности напряжённого состояния транзисторов для временного анализа с учётом электротемпературной нестабильности // Информационные технологии. – 2009, № 7, С. 32–38.
17.	Marculescu R., Marculescu D., Pedram M. Switching Activity Analysis Considering Spatiotemporal Correlations // in Proc.  ICCAD-1994. P. 294-299.
18.	Huang H.-M., Wen H.-P. W. Fast-Yet-Accurate Statistical Soft-Error-Rate Analysis Considering Full-Spectrum Charge Collection / IEEE Design & Test, March/April 2013, pp. 77-86. 
19.	Кодирование информации (двоичные коды). Справочник // Под ред. проф. Н. Т. Березнюка. ‑ Харьков: Вища школа. ‑ 1978. 
20.	Дадаев Ю. Г. Теория арифметических кодов. ‑ М.: Радио и связь. – 1981.
1.	Хетагуров1.	 Я. А., Руднев Ю. П., Повышение надёжности цифровых устройств методами избыточного кодирования. – М: Энергия. ‑1974г.21.