УСТРОЙСТВО ФОРМИРОВАНИЯ И ВОССТАНОВЛЕНИЯ МОДИФИЦИРОВАННОГО КОДА ХЕММИНГА ДЛЯ 32-РАЗРЯДНЫХ ДВОИЧНЫХ ЧИСЕЛ Российский патент 2023 года по МПК H03M13/19 

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

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

При формировании кодового слова по Хеммингу к М значащим разрядам двоичного числа добавляют разряды проверки в количестве K, определяемом из неравенства (1).

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

Разрядные позиции в кодовом слове имеют номера, следующие подряд от единицы до М+K. Проверочные разряды с индексами i=0, 1, 2, 3, … K-1 занимают позиции с номерами равными 2 в степени i, то есть 1, 2, 4, 8, … 2^K-1 соответственно. Остальные М позиций в произвольном порядке занимают значащие разряды кодируемого числа.

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

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

Модифицированный код Хемминга [1] позволяет обнаруживать еще и двойные ошибки, он отличается от своего прототипа добавлением еще одного разряда проверки, который является дополнением до четности всего кодового слова Хемминга.

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

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

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

Из неравенства (1) следует, что для кодирования 32 разрядов данных необходимо 6 проверочных разрядов. Этого количества хватает и для значительно большего числа разрядов - 57, что дает возможность выбора используемых позиций кодового числа таким образом, чтобы сократить количество слагаемых по модулю два при вычислении проверочных разрядов.

Двоичное представление номера каждой позиции значащего разряда данных в кодовом слове содержит единицы в количестве от двух до шести и оно соответствует количеству проверочных сумм, в которые входит данный разряд. Например, разряд на позиции 001010 входит в две суммы для вычисления k₁ и k₃, а на позиции 101111 - в пять сумм для k₀, k₁, k₂, k₃ и k₅. Уменьшение числа слагаемых в контрольных суммах достигается предпочтением позиций с номерами с меньшим количеством единиц. А разряды на позициях с номерами, содержащими по три и пять единиц, вообще не входят в дополнительную проверочную сумму. Среди 6-разрядных двоичных чисел таких всего 26.

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

Поясним, как в случае K=7 сократить количество слагаемых при вычислении проверочных разрядов. Из 120-и значащих разрядов 21 разряд входит в контрольные суммы только по два раза, 35 - по три, еще 35 - по четыре, еще 21 разряд используется по пять раз, 7 -по шесть и один - во всех семи суммах. Если позиции кодового слова для 32-х значащих разрядов выбрать из тех 35-и, каждая из которых рассматривается при вычислении только трех проверочных разрядов, то вычислять дополнительную проверочную сумму не потребуется, а общее число слагаемых в семи проверочных суммах будет равно 3 × 32+7, то есть 103.

Пример такого решения описан в патенте США №5313475, НПК 371/40.1, 371/40.2, 371/51.1, МПК Н03М 13/00, опубл. 17 мая 1994 г. [2]. По технической сущности данное устройство наиболее близко заявляемому изобретению.

Устройство содержит вычислитель разрядов проверки, входы которого в количестве 32 являются входами разрядов данных устройства, а семь выходов - его выходами разрядов проверки для подключения к соответствующим входам устройства передачи или хранения данных, вычислитель адреса ошибки, входы которого в количестве 39 соединены со входами приема 32-х разрядов данных и семи разрядов проверки с выходов устройства передачи или хранения данных, дешифратор адреса ошибки, семь входов которого подключены к семи выходам вычислителя адреса ошибки, схему коррекции, состоящую из тридцати девяти элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ, первые входы которых являются тридцатью двумя входами разрядов данных и семью входами разрядов проверки и соединены со входами приема тридцати двух разрядов данных и семи разрядов проверки с выходов устройства передачи или хранения данных, а вторые входы элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ являются тридцатью девятью входами адреса ошибки схемы коррекции и соединены с соответствующими выходами дешифратора адреса ошибки, выходы элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ являются выходами устройства для тридцати двух исправленных разрядов данных и семи исправленных разрядов проверки, формирователь сигналов об ошибках, семь входов которого подключены к семи выходам вычислителя адреса ошибки, а выходы являются выходами устройства для сигнала об ошибке и сигнала о двойной ошибке,

Вычислитель разрядов проверки состоит из семи блоков контроля четности, содержащих по пятнадцать элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ, объединенных в древовидную цепь, в которой первые и вторые входы элементов первого каскада подключены ко входам разрядов данных, а выходы элементов четвертого каскада каждого из семи блоков являются выходами с нулевого по шестой разрядов проверки.

Разряды проверки k₀, … k₆ вычисляются как логические суммы по модулю 2 из переменных d₀, … d₃₁, представляющих разряды данных в соответствии с таблицей 1, где вхождение каждой переменной d_i в определенные суммы k_j обозначены символами «х» на пересечении соответствующего d_i столбца и соответствующей k_j строки.

Из таблицы видно, что в логические суммы, соответствующие разрядам k₀, k₁, k₂, k₃, k₄, k₅, входят по 14 слагаемых, а в сумме для k₆ их 12, в то время как содержащиеся в вычислителе разрядов проверки блоки контроля четности имеют по 16 логических входов, часть которых не используется и на них приходится подавать постоянные сигналы логического нуля. Это приводит к избыточности логических элементов в устройстве и является его недостатком.

Вычислитель адреса ошибки составляют семь блоков контроля четности, содержащих по пятнадцать элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ, объединенных в древовидную цепь, в которой первые и вторые входы элементов первого каскада подключены ко входам принимаемых разрядов данных, а также семь инверторов и семь выходных элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ, первые входы которых соответственно подключены к выходам семи блоков контроля четности, вторые входы - ко входам с нулевого по шестой принимаемых разрядов проверки, а выходы соответственно являются выходами повторений с нулевого по шестой разрядов кода адреса ошибки и соединены со входами инверторов, выходы которых являются выходами инверсий с нулевого по шестой разрядов кода адреса ошибки соответственно.

Обнаружение ошибок в принимаемых разрядах данных и разрядах проверки в устройстве осуществляется посредством сравнения логических уровней принятых разрядов проверки с заново вычисленными из принятых разрядов данных. Эту операцию выполняют содержащиеся в вычислителе адреса ошибки выходные элементы ИСКЛЮЧАЮЩЕЕ 2ИЛИ и блоки контроля четности, эквивалентные аналогичным блокам вычислителя разрядов проверки.

Такое выполнение вычислителя адреса ошибки еще более избыточно, принятые разряды проверки могли бы поступать на один из неиспользуемых входов каждого соответствующего блока контроля четности и выходные элементы ИСКЛЮЧАЮЩЕЕ 2ИЛИ тогда бы не понадобились.

При несовпадении принятых и заново вычисленных разрядов проверки соответствующие выходные элементы ИСКЛЮЧАЮЩЕЕ 2ИЛИ вырабатывают логические единицы.

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

В случаях двукратных ошибок выходные элементы ИСКЛЮЧАЮЩЕЕ 2ИЛИ выдадут четное количество логических единиц. Возможно несколько вариантов.

Две единицы появятся, когда ошибка произошла в двух разрядах данных, вместе вошедших в две общие проверочные суммы, четность которых не меняется, и по отдельности в две проверочные суммы, дающие эти единицы. Например, d₀ и d₁ вместе входящие в суммы для k₁, k₃, а по отдельности - соответственно для k₄ и k₀. Также когда ошибки случились в двух проверочных разрядах и когда с ошибками принят один проверочный разряд и один, входящий в соответствующую ему сумму, разряд данных, так, ошибки k₀ и d₁ меняет четность при проверке k₀, k₁ и k₃, но значение суммы для k₀ меняется вместе со значением k₀.

Четыре единицы имеют место в случаях двойной ошибки в разрядах данных, которые вместе входят в одну проверочную сумму и по отдельности в четыре разные, например, в d₁ и d₉, которые входят в общую сумму k₀ и в разные суммы k₁, k₃ и k₂, k₄ соответственно. А еще при одной ошибке в проверочном разряде и в не связанном с ним разряде данных, k₀ и d₀, например.

Шесть единиц соответствуют случаю ошибки в двух разрядах данных, входящих в разные контрольные суммы как d₁ и d₈, присутствующие в суммах для k₀, k₁, k₃ и k₂, k₄, k₅ соответственно.

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

Однако в случаях, когда меняется четность одной или трех контрольных сумм тройные ошибки идентифицируются как одиночные. Например, когда ошибки происходят в трех разрядах данных, по два раза входящих в три общие контрольные суммы и в три суммы по отдельности, как d₁, d₄, d₂₈, дважды вошедшие в суммы для k₀, k₁, k₂ и по одному разу - для k₃, k₄, k₅. Четность меняется только в суммах для k₃, k₄, k₅ и ошибка будет ложно воспринята как одиночная в вошедшем в эти суммы разряде d₁₉. Если три разряда данных с ошибками по два раза входят в четыре контрольные суммы, а один из них еще и в пятую сумму. Так d₀, d₁, d₉, парами d₁, d₉ и d₀, d₉ представлены в суммах для k₀ и k₄ соответственно и парой d₀, d₁ в суммах для k₁ и k₃ одновременно, а также одним разрядом d₉ - в сумме для k₂, изменение четности которой ложно идентифицируется как ошибка разряда проверки k_{2 Дешифратор адреса ошибки состоит из 39-ти элементов 7И, входы которых в различных комбинациях соединены со входами для повторений и инверсии семи разрядов кода адреса ошибки, а выходы являются выходами адреса ошибки. Входы элементов 7И подключены в соответствии с таблицей 1, комбинации из трех подключений к прямым и четырех - к инверсным входам соответствуют адресам разрядов данных, а комбинации из одного подключения ко входу повторения и шести входам инверсий соответствуют адресам проверочных разрядов.}

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

Формирователь сигналов об ошибках состоит из элемента 7ИЛИ, входы которого соединены с выходами повторений разрядов кода адреса ошибки, а выход является выходом сигнала об ошибке, четырех элементов 8ИЛИ-НЕ и элемента 7ИЛИ-НЕ, входы которых в общем количестве 39 подключены к выходам адреса ошибки, а выходы соединены с пятью входами элемента 6И, шестой вход которого подключен к выходу сигнала об ошибке. Выход элемента 6И является выходом сигнала о двойной ошибке.

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

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

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

Технический результат достигается тем, что в устройство формирования и восстановления модифицированного кода Хемминга для 32-разрядных двоичных чисел, содержащее вычислитель разрядов проверки, входы которого в количестве 32 являются входами разрядов данных устройства, а семь выходов - его выходами разрядов проверки для подключения к соответствующим входам устройства передачи или хранения данных, вычислитель адреса ошибки, входы которого в количестве 39 соединены со входами приема 32-х разрядов данных и семи разрядов проверки с выходов устройства передачи или хранения данных, дешифратор адреса ошибки, семь входов которого подключены к семи выходам вычислителя адреса ошибки, схему коррекции, состоящую из тридцати девяти элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ, первые входы которых соединены со входами приема 32-х разрядов данных и семи разрядов проверки с выходов устройства передачи или хранения данных, а вторые входы соединены с соответствующими выходами дешифратора адреса ошибки, выходы элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ являются выходами устройства для 32-х исправленных разрядов данных и семи исправленных разрядов проверки, формирователь сигналов об ошибках, семь входов которого подключены к семи выходам вычислителя адреса ошибки, а выходы являются выходами устройства для сигнала об отсутствии ошибок, сигнала об одиночной ошибке и сигнала о двойной ошибке, внесены следующие отличия.

Вычислитель разрядов проверки состоит из тридцати одного элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, первые и вторые входы первых четырнадцати из которых в порядке возрастания номеров подключены ко входам разрядов данных соответственно с четными и нечетными номерами, следующими в порядке возрастания от 0 до 27, первые входы с 15-го по 31-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада соответственно подключены ко входам разрядов данных с номерами 11, 17, 15, 21, 29, 0, 22, 1, 23, 28, 2, 8, 30, 3, 9, 7,13, а их вторые входы - ко входам разрядов данных с номерами 14, 20, 18, 24, 30, 19, 25, 4, 26, 29, 5, 27, 31, 6, 12, 10, 16, четырнадцати элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, первые и вторые входы первых семи из которых в порядке возрастания номеров подключены к выходам элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада соответственно с нечетными и четными номерами, следующими по порядку от 1 до 14, первые входы 8-го и 10-го элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада соответственно подключены ко входам 28-го и 31-го разрядов данных, а 9-го и с 11-го по 14-й - соответственно к выходам 18-го, 23-го, 26-го, 28-го и 30-го элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, вторые входы с 8-го по 14-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада соответственно подключены к выходам 16-го, 19-го, 21-го, 24-го, 27-го, 29-го и 31-го элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, четырнадцати элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада, первые входы первых семи из которых в порядке возрастания номеров подключены к выходам 7-го и с 1-го по 6-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, а вторые входы - к выходам с 1-го по 7-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, первые входы с 8-го по 14-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада соответственно подключены к выходам 15-го, 17-го, 20-го, 22-го, 25-го, 24-го и 27-го элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, а вторые входы - к выходам с 8-го по 14-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, и с 1-го по 7-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ четвертого каскада, первые входы которых соответственно подключены к выходам с 1-го по 7-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада, вторые входы - к выходам с 8-го по 14-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада, а выходы соответственно являются выходами с нулевого по шестой разрядов проверки.

Вычислитель адреса ошибки состоит из тридцати одного элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, первые и вторые входы первых четырнадцати из которых в порядке возрастания номеров подключены ко входам приема разрядов данных с четными и нечетными номерами соответственно, следующими по порядку от 0 до 27, первые входы с 15-го по 31-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада соответственно подключены ко входам приема разрядов данных с номерами 11, 17, 15, 21, 29, 0, 22, 1, 23, 28, 2, 8, 30, 3, 9, 7, 13, а их вторые входы - ко входам приема разрядов данных с номерами 14, 20, 18, 24, 30, 19, 25, 4, 26, 29, 5, 27, 31, 6, 12, 10, 16, двадцати одного элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, первые и вторые входы первых семи из которых в порядке возрастания номеров подключены к выходам элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада соответственно с нечетными и четными номерами, следующими по порядку от 1 до 14, первые входы элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада с четными номерами в диапазоне от 8 до 21 соответственно подключены ко входам приема с нулевого по шестой разрядов проверки, а с нечетными номерами - соответственно ко входу приема 28-го разряда данных, к выходу 18-го элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, ко входу приема 31-го разряда данных и к выходам 23-го, 26-го, 28-го и 30-го элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, вторые входы с 8-го по 21-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада соответственно подключены к выходам 15-го, 16-го, 17-го, 19-го, 20-го, 21-го, 22-го, 24-го, 25-го, 27-го, 24-го, 29-го, 27-го, 31-го элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, четырнадцати элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада, первые входы первых семи из которых в порядке возрастания номеров подключены к выходам 7-го и с 1-го по 6-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, а вторые входы - к выходам с 1-го по 7-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, первые и вторые входы с 8-го по 14-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада подключены к выходам элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада с четными и нечетными номерами соответственно из диапазона от 8 до 21, и с 1-го по 7-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ четвертого каскада, первые входы которых соответственно подключены к выходам с 1 -го по 7-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада, вторые входы - к выходам с 8-го по 14-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада, а прямые и инверсные выходы соответственно являются выходами повторений и инверсий с нулевого по шестой разрядов кода адреса ошибки.

Дешифратор адреса ошибки состоит из двенадцати элементов 2ИЛИ-НЕ первого каскада, первые входы которых по порядку номеров элементов соединены со входами дешифратора для повторения 0-го, инверсии 0-го, повторения 0-го, инверсии 0-го, повторения 4-го, инверсии 4-го, повторения 4-го, инверсии 4-го, повторения 1-го, инверсии 1-го, повторения 1-го, инверсии 1-го разрядов кода адреса ошибки, а вторые входы - следующими подряд парами - ко входам для повторения 2-го, инверсии 2-го, повторения 5-го, инверсии 5-го, повторения 3-го, инверсии 3-го разрядов кода адреса ошибки, двадцати элементов 2И-НЕ второго каскада, первые входы которых по порядку номеров элементов подключены к выходам элементов 2ИЛИ-НЕ первого каскада с номерами 1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 2, 1 и 9, 10, 11, 12, 11, 10, 9, вторые входы с 1-го по 4-й элементов 2И-НЕ второго каскада подключены к выходу элемента 2ИЛИ-НЕ первого каскада с номером 5, с 5-го по 7-й - с номером 6, с 8-го по 10-й-с номером 7, с 11-го по 13-й - с номером 8, вторые входы с 14-го по 17-й и с 18-го по 20-й элементов 2И-НЕ второго каскада соответственно соединены и подключены ко входам дешифратора для инверсии и повторения 6-го разряда кода адреса ошибки, тридцати девяти элементов 2(НЕ)-2И третьего каскада, первые входы которых по порядку номеров элементов подключены к выходам элементов 2И-НЕ второго каскада с номерами 4, 2, 6, 9, 3, 7, 10, 3, 7, 10, 3, 4, 13, 5, 6, 5, 13, 12, 13, 11, 9, 8, 10, 8, 2, 4, 2, 6, 9, 8, 5, 7, 2, 1, 3, 1, 5, 8, 1, а вторые входы - к выходам элементов 2И-НЕ второго каскада с номерами 15, 17, 15, 15, 17, 15, 15, 19, 16, 16, 18, 16, 16, 18, 16, 17, 20, 14, 15, 14, 20, 19, 20, 18, 19, 20, 18, 20, 16, 17, 19, 20, 14, 15, 14, 16, 14, 14, 20, выходы элементов 2(НЕ)-2И третьего каскада являются выходами адреса ошибки.

Формирователь сигналов об ошибках состоит из четырех 7-входовых пороговых логических элементов с порогами 1, 2, 3, 4, входы которых соответственно соединены и подключены к семи выходам вычислителя адреса ошибки, логического элемента 2(2И)-2ИЛИ, входы первого объединения 2И которого соответственно подключены к прямому и к инверсному выходам пороговых логических элементов с порогами 1 и 2, а входы второго объединения 2И - к прямому и к инверсному выходам пороговых логических элементов с порогами 3 и 4, выход элемента 2(2И)-2ИЛИ является выходом сигнала об одиночной ошибке, логического элемента 2И-2ИЛИ, входы объединения 2И которого соответственно подключены к прямому и к инверсному выходам пороговых логических элементов с порогами 2 и 3, а внешний вход объединения 2ИЛИ - к прямому выходу порогового логического элемента с порогом 4, выход элемента 2И-2ИЛИ является выходом сигнала о двойной ошибке, инверсный выход порогового логического элемента с порогом 1 является выходом сигнала об отсутствии ошибок.

Каждая пара из связанных между собой элемента 2(НЕ)-2И третьего каскада дешифратора адреса ошибки и элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ схемы коррекции состоит из шести МОП-транзисторов обогащенного типа с индуцированными каналами р-типа проводимости и пяти МОП-транзисторов обогащенного типа с индуцированными каналами n-типа проводимости, истоки первого, четвертого, пятого р-МОП-транзисторов подключены к шине положительного напряжения питания, а истоки первого, второго, пятого n-МОП-транзисторов - к шине нулевого потенциала, сток первого р-МОП-транзистора соединен с истоком второго р-МОП-транзистора, сток которого вместе со стоками первого, второго n-МОП-транзисторов и истоками шестого р- и третьего n-МОП-транзисторов соединены с затворами четвертых р- и n-МОП-транзисторов, сток четвертого р-МОП-транзистора подключен к истоку третьего МОП-транзистора аналогичного типа, сток пятого р-МОП-транзистора соединен с истоком и стоком соответственно четвертого и пятого n-МОП-транзисторов и с затворами третьих р- и n-МОП-транзисторов, затворы первых и вторых МОП-транзисторов обоих типов соответственно соединены и являются первым и вторым входами элемента 2(НЕ)-2И, а соединенные затворы пятого, шестого р-МОП- и пятого n-МОП-транзисторов - первым входом элемента ИСКЛЮЧАЮЩЕЕ-2ИЛИ, стоки третьего и шестого р-МОП- и третьего, четвертого n-МОП-транзисторов соединены и являются выходом элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ.

Конструктивно каждая пара из связанных между собой элемента 2(НЕ)-2И третьего каскада дешифратора адреса ошибки и элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ схемы коррекции выполнена в виде смежных продольными сторонами областей МОП-структур р- и n-типа, поперек которых, разделяя их на области стоков-истоков соответствующих типов, проходят пять полосок затворов, которые, пересекая области р- и n-МОП-структур в порядке номеров, образуют области каналов с первых по пятые р- и n-МОП-транзисторов соответственно и шестая полоска затвора, пересекающая область МОП-структур р-типа между второй и третьей полосками затворов, образуя область канала шестого р-МОП-транзистора, крайняя область истока со стороны первой полоски затворов и область истоков между четвертой и пятой полосками затворов в области р-МОП-структур подключены к шине положительного напряжения питания, а область истоков между первой и второй полосками затворов и крайняя со стороны пятой полоски затворов область истока в области n-МОП-структур - к шине нулевого потенциала, область стока-истока, расположенная между второй и шестой полосками затворов в области р-МОП-структур, крайняя со стороны первой полоски затворов область стока и область стока-истока между второй и третьей полосками затворов в области n-МОП-структур электрически связаны с четвертой полоской затворов, а крайняя со стороны пятой полоски затворов область стока в области р-МОП-структур и область стока-истока между четвертой и пятой полосками затворов в области n-МОП-структур - с третьей полоской затворов, первая и вторая полоски затворов соответственно подключены к первому и второму входам элемента 2(НЕ)-2И, а пятая и шестая полоски затворов - к первому входу элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ, области стоков, расположенные между третьей и шестой полосками затворов в области р-МОП-структур и между третьей и четвертой полосками затворов в области n-МОП-структур, электрически связаны с выходом элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ.

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

Отличительными признаками изобретения являются состав используемых логических элементов, их электрические связи, схема и конструктивное выполнение элементов третьего каскада дешифратора адреса ошибки, скомбинированных с элементами ИСКЛЮЧАЮЩЕЕ 2ИЛИ схемы коррекции.

Изобретение поясняют чертежи, на которых изображены структурная схема устройства - фиг. 1 и функциональные электрические схемы его структурных блоков: фиг. 2, 3 - вычислителей разрядов проверки и адреса ошибки соответственно, Фиг. 4 - первой и второй ступеней дешифратора адреса ошибки, фиг. 5 - схемы коррекции с элементами третьей ступени дешифратора адреса ошибки и формирователя сигналов об ошибках на фиг. 6. Фиг. 7 и 8 представляют функциональную и принципиальную электрические схемы совмещенных элементов 2(НЕ)-2И третьего каскада дешифратора адреса ошибки и ИСКЛЮЧАЮЩЕЕ 2ИЛИ схемы коррекции, а фиг. 9 и 10 - схемы их конструктивного выполнения в отдельной паре и в группе из трех пар.

Устройство формирования и восстановления модифицированного кода Хемминга для 32-разрядных двоичных чисел содержит вычислитель разрядов проверки, входы которого в количестве 32 являются входами разрядов d₀, … d₃₁ данных устройства, а семь выходов - его выходами разрядов k₀, … k₆ проверки для подключения к соответствующим входам устройства передачи или хранения данных, вычислитель адреса ошибки, входы которого в количестве 39 соединены со входами приема 32-х разрядов х₀, … х₃₁ данных и семи разрядов r₀, … r₆ проверки с выходов устройства передачи или хранения данных, дешифратор адреса ошибки, входы которого подключены к прямым и инверсным выходам s₀, … s₆ и s₀, … s₆ вычислителя адреса ошибки, схему коррекции с тридцатью девятью входами, соединенными со входами приема тридцати двух разрядов х₀, … х₃₁ данных и семи разрядов r₀, … r₆ проверки с выходов устройства передачи или хранения данных, и тридцатью девятью входами адреса ошибки, соединенными с соответствующими выходами дешифратора адреса ошибки, выходы схемы коррекции являются выходами устройства для тридцати двух исправленных разрядов d₀, … d₃₁ данных и семи исправленных разрядов k₀, … k₆ проверки, формирователь сигналов об ошибках, входы которого подключены к выходам s₀, … s₆ вычислителя адреса ошибки, а выходы являются выходами устройства для сигнала об отсутствии ошибок, сигнала об одиночной ошибке и сигнала о двойной ошибке.

Вычислитель разрядов проверки состоит из тридцати одного элемента 1-1, … 1-31 ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, четырнадцати элементов 2-1, … 2-14 ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, четырнадцати элементов 3-1, … 3-14 ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада, семи элементов 4-1, … 4-7 ИСКЛЮЧАЮЩЕЕ 2ИЛИ четвертого каскада. Первые и вторые входы элементов 1-1, … 1-14 в порядке возрастания номеров подключены ко входам d₀, … d₂₇ разрядов данных соответственно с четными и нечетными номерами, первые входы элементов 1-15, … 1-31 соответственно подключены ко входам d₁₁, d₁₇, d₁₅, d₂₁, d₂₉, d₀, d₂₂, d₁, d₂₃, d₂₈, d₂, d₈, d₃₀, d₃, d₉, d₇, d₁₃ разрядов данных, а их вторые входы - ко входам d₁₄, d₂₀, d₁₈, d₂₄, d₃₀, d₁₉, d₂₅, d₄, d₂₆, d₂₉, d_5l d₂₇, d₃₁, d₆, d₁₂, d₁₀, d₁₆ разрядов данных. У элементов 2-1, … 2-7 в порядке возрастания номеров первые и вторые входы подключены к выходам элементов 1-1, … 1-14 соответственно с нечетными и четными номерами, первые входы у элементов 2-8 и 2-10 соответственно подключены ко входам d₂₈ и d₃₁ разрядов данных, а у 2-9 и 2-11, … 2-14 - соответственно к выходам элементов 1-18, 1-23, 1-26, 1-28, 1-30, вторые входы элементов 2-8, … 2-14 соответственно подключены к выходам элементов 1-16,1-19,1-21, 1- 24, 1-27, 1-29 1-31. У элементов 3-1, … 3-7 в порядке возрастания номеров первые входы подключены к выходам элементов 2-7 и 2-1, … 2-6, а вторые входы - к выходам элементов 2-1, … 2-7. Первые входы элементов 3-8, … 3-14 соответственно подключены к выходам элементов 1-15, 1-17, 1-2, 1-22, 1-25, 1-24, 1-27, а вторые входы - к выходам элементов 2-8, … 2-14. Первые входы элементов 4-1, … 4-7 соответственно подключены к выходам элементов 3-1, … 3-7, вторые входы - к выходам элементов 3-8, … 3-14, а выходы соответственно являются выходами k₀, … k₆ разрядов проверки.

Вычислитель разрядов проверки построен по древовидной структурной схеме. Разряды проверки k₀, … k₆ вычисляются как логические суммы по модулю 2 из переменных d₀, … d₃₁, представляющих разряды данных в соответствии с Таблицей 2.

Логические суммы, соответствующие разрядам k₁, k₃, k₄, k₅, k₆, объединяют по 14 слагаемых, а в суммах для k₀ и k₂ их по 13.

Обведенные в рамки комбинации переменных одновременно входят в две логические суммы, что позволяет объединить цепи формирования сумм этих переменных. В схеме фиг. 2 цепь из элементов 1-1, 1-2, 2-1 используется для формирования сигналов разрядов k₀ и k₁ 1-3, 1-4, 2-2 - для k₁ и k₂, 1-5, 1-6, 2-3 - для k₂ и k₃, 1-7, 1-8, 2-4-для k₃ и k₄, 1-9, 1-10, 2-5 - для k₄ и k₅, 1-11, 1-12, 2-6-для k₅ и k₆, 1-13, 1-14, 2-7 - для k₀ и k₆, элемент 1-24 входит в цепи для k₃ и k₅, а - 1-27 - для k₄ и k₆. Сложение общих частей сумм с остальными переменными в вычислителе разряда проверки выполняют индивидуальные древовидные цепи из элементов 1-15, 1-16, 2-8, 3-1, 3-8, 4-1 для k₀, 1-17, 1-18, 1-19, 2-9, 3-2, 3-9, 4-2 для k₁, 1-20, 1-21, 2-10, 3-3, 3-10, 4-3 для k₂, 1-22, 1-23, 2-11, 3-4, 3-11,4-4 для k₃, 1-25, 1-26, 2-12, 3-5, 3-12, 4-5 для k₄, 1-28, 1-29, 2-13, 3-6, 3-13, 4-6 для k₅, 1-30, 1-31, 2-14, 3-7, 3-14, 4-7 для k₆.

Вычислитель адреса ошибки состоит из тридцати одного элемента 5-1, … 5-31 ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, двадцати одного элемента 6-1, … 6-21 ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, четырнадцати элементов 7-1, … 7-14 ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада, семи элементов 8-1, … 8-7 ИСКЛЮЧАЮЩЕЕ 2ИЛИ четвертого каскада. Первые и вторые входы элементов 5-1, … 5-14 в порядке возрастания номеров подключены ко входам х₀, … х₂₇ разрядов данных соответственно с четными и нечетными номерами, первые входы элементов 5-15, … 5-31 соответственно подключены ко входам х₁₁, х₁₇, х₁₅, х₂₁, х₂₉, х₀, х₂₂, х₁, х₂₃, х₂₈, х₂, х₈, х₃₀, х₃, х₉, х₇, х₁₃ разрядов данных, а их вторые входы - ко входам x₁₄, x₂₀, x₁₈, x₂₄, x₃₀, x₁₉, x₂₅, x₄, x₂₆, x₂₉, x₅, x₂₇, x₃₁, x₆, x₁₂, x₁₀, x₁₆ разрядов данных. У элементов 6-1, … 6-7 в порядке возрастания номеров первые и вторые входы подключены к выходам элементов 5-1, … 5-14 соответственно с нечетными и четными номерами, первые входы у элементов 6-8, 6-10, 6-12, 6-14, 6-16, 6-18, 6-20 соответственно подключены ко входам r₀, … r₆ разрядов проверки, а с номерами 6-9, 6-11, 6-13, 6-15, 6-17, 6-19, 6-21 - соответственно ко входу х₂₈ разряда данных, к выходу элемента 5-18, ко входу х₃₁ разряда данных и к выходам элементов 5-23, 5-26, 5-28, 5-30. Вторые входы элементов 6-8, … 6-21 соответственно подключены к выходам элементов 5-15, … 5-17, 5-19, … 5-22, 5-24, 5-25, 5-27, 5-24, 5-29, 5-27, 5- 31. У элементов 7-1, … 7-7 в порядке возрастания номеров первые входы подключены к выходам элементов 6-7 и 6-1, … 6-6, а вторые входы - к выходам элементов 6-1, … 6-7. Первые и вторые входы элементов 7-8, … 7-14 подключены к выходам элементов 6-8, … 6-21 соответственно с четными и нечетными номерами. Первые входы элементов 8-1, … 8-7 соответственно подключены к выходам элементов 7-1, … 7-7, вторые входы - к выходам элементов 7-8, … 7-14. Прямые и инверсные выходы элементов 8-1, … 8-7 соответственно являются выходами повторений и инверсий s₀, … s₆ разрядов кода адреса ошибки.

Вычислитель адреса ошибки формирует каждый из разрядов проверки s_i, i=0, … 6 как суммы по модулю 2 из принимаемых с выходов устройства передачи или хранения данных разрядов данных х₀, … х₃₁ согласно Таблице 3 и разряда проверки r_i с тем же номером из ряда i=0, … 6. В схеме фиг. 3 цепь из элементов 5-1, 5-2, 6-1 используется для формирования сигналов разрядов s₀ и s₁, 5-3, 5-4, 6-2 - для s₁ и s₂, 5-5, 5-6, 6-3 - для s₂ и s₃, 5-7, 5-8, 6-4 - для s₃ и s₄, 5-9, 5-10, 6-5 - для s₄ и s₅, 5-11, 5-12, 6-6 - для s₅ и s₆, 5-13, 5-14,6-7 -для s₀ и s₆, элемент 5-24 входит в цепи для s₃ и s₅, а - 5-27 - для s₄ и s₆. Общие части сумм с остальными переменными в вычислителе адреса ошибки складывают по модулю 2 отдельные древовидные цепи из элементов 5-15, 5-16, 6-8, 6-9, 7-1, 7-8, 8-1 для s₀, 5-17, 5-18, 5-19, 6-10, 6-11, 7-2, 7-9, 8-2 для s₁, 5-20, 5-21, 6-12, 6-13, 7-3, 7-10, 8-3 для s₂, 5-22, 5-23, 6-14, 6-15, 7-4, 7-11,8-4 для s₃, 5-25, 5-26, 6-16, 6-17, 7-5, 7-12, 8-5 для s₄, 5-28, 5-29, 6-18, 6-19, 7-6, 7-13, 8-6 для s₅, 5-30, 5-31, 6-20, 6-21, 7-7, 7-14, 8-7 для s₆.

Поясняющая работу вычислителя адреса ошибки Таблица 3 совпадает с описывающей работу вычислителя разрядов проверки Таблицей 2, если рассматривать принимаемые и отправляемые устройством передачи или хранения данных переменные d₀, … d₃₁, k₀, … k₆ и x₀, … х₃₁, r₀, … r₆ как соответственно эквивалентные. Это обеспечивает выполнение вычислителем адреса ошибки функции по сравнению разрядов проверки r₀, … r₆, принятых с выхода устройства передачи или хранения данных, с заново вычисленными из также принятых разрядов данных х₀, … х₃₁. В случае их совпадения соответствующие сигналы s₀, … s₆ кода адреса ошибки принимают нулевые логические значения.

Наличие ошибки в одном из разрядов r₀, … r₆ или х₀, … х₃₁ отразится единичными логическими значениями переменных s₀, … s₆, в суммы для определения которых входит ошибочная переменная. Так как каждая из переменных r₀, … r₆ входит только в одну сумму для s₀, … s₆ с аналогичным номером, однократная ошибка в r_i, приведет к единичному значению s_i, а однократная ошибка одной из переменных x_i обратит в логические единицы три из переменных s₀, … s₆, в суммы для вычисления которых входит эта переменная, согласно Таблице 3.

Дешифратор адреса ошибки состоит из двенадцати элементов 9-1, … 9-12 2ИЛИ-НЕ первого каскада, двадцати элементов 10-1, … 10-20 2И-НЕ второго каскада, тридцати девяти блоков 11-1, … 11-39, каждый из которых объединяет элемент 2(НЕ)-2И третьего каскада дешифратора с элементом ИСКЛЮЧАЮЩЕЕ 2ИЛИ из состава схемы коррекции таким образом, что выход элемента 2(НЕ)-2И подключен к первому входу элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ.

Первые входы элементов 9-1, … 9-12 по порядку номеров элементов соединены со входами дешифратора для повторения и инверсии 0-го разряда проверки, s₄, повторения и инверсии 4-го разряда проверки, s₁, s₁, для повторения и инверсии 1-го разряда проверки, а вторые входы - следующими подряд парами - ко входам s₂ для повторения 2-го, инверсии 2-го, s₅ повторения 5-го, инверсии 5-го, s₃ повторения 3-го, инверсии 3-го разрядов проверки. Первые входы элементов 10-1, … 10-20 по порядку номеров элементов подключены к выходам элементов 9-1, 9-2, 9-3, 9-4, 9-1, 9-2, 9-3, 9-1, 9-2, 9-3, 9-3, 9-2, 9-1, 9-9, 9-10, 9-11, 9-12, 9-11, 9-10, 9-9. Вторые входы элементов 10-1, … 10-13 подключены к выходам элементов 9-5, 9-5, 9-5, 9-5, 9-6, 9-6, 9-6, 9-7, 9-7, 9-7, 9-8, 9-8, 9-8. Вторые входы элементов 10-14, … 10-17 и элементов 10-18, … 10-20 соответственно соединены и подключены ко входам s₆ и s₆ дешифратора для инверсии и повторения 6-го разряда проверки. Первые входы элементов 2(НЕ)-2И в блоках 11-1, … 11-39 по порядку номеров элементов подключены к выходам элементов 10-4, 10-2, 10-6, 10-9, 10-3, 10-7, 10-10, 10-3, 10-7, 10-10, 10-3, 10-4, 10-13, 10-5, 10-6, 10-5, 10-13, 10-12, 10-13, 10-11, 10-9, 10-8, 10-10, 10-8, 10-2, 10-4, 10-2, 10-6, 10-9, 10-8, 10-5, 10-7, 10-2, 10-1, 10-3, 10-1, 10-5, 10-8, 10-1, а вторые входы - к выходам элементов 10-15, 10-17, 10-15, 10-15, 10-17, 10-15, 10-15, 10-19, 10-16, 10-16, 10-18, 10-16, 10-16, 10-18, 10-16, 10-17, 10-20, 10-14, 10-15, 10-14, 10-20, 10-19, 10-20, 10-18, 10-19, 10-20, 10-18, 10-20, 10-16, 10-17, 10-19, 10-20, 10-14, 10-15, 10-14, 10-16, 10-14, 10-14, 10-20. Вторые входы элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ в блоках 11-1, … 11-39 соответственно подключены ко входам х₀, … х₃₁ разрядов данных и r₀, … r₆ разрядов проверки, а выходы - являются выходами устройства для тридцати двух исправленных разрядов d₀, … d₃₁ данных и семи исправленных разрядов k₀, … k₆ проверки.

Формирователь сигналов об ошибках состоит из четырех 7-входовых пороговых логических элементов 12, 13, 14, 15 с порогами 1, 2, 3, 4, входы которых соответственно соединены и подключены к семи выходам s₀, … s₆ вычислителя адреса ошибки, логического элемента 16 2(2И)-2ИЛИ и логического элемента 17 2И-2ИЛИ. У элемента 16 входы первого объединения 2И соответственно подключены к прямому и к инверсному выходам логических элементов 12 и 13, а входы второго объединения 2И - к прямому и к инверсному выходам логических элементов 14 и 15, выход элемента 16 является выходом сигнала об одиночной ошибке. У элемента 17 входы объединения 2И соответственно подключены к прямому и к инверсному выходам логических элементов 13 и 14, а внешний вход объединения 2ИЛИ - к прямому выходу логического элемента 15, выход элемента 17 является выходом сигнала о двойной ошибке. Инверсный выход логического элемента 12 является выходом сигнала об отсутствии ошибок.

Отсутствие ошибок в принятых с выходов устройства передачи или хранения данных разрядах х₀, … х₃₁ и r₀, … r₆ формирователь сигналов об ошибках идентифицирует по отсутствию единичных значений среди сигналов s₀, … s₆. Такой принцип работы позволяет однозначно констатировать отсутствие ошибок в одном, двух и трех разрядах из х₀, … х₃₁ и r₀, … r₆ общим количеством 39.

Одиночная ошибка в любом из разрядов данных х₀, … х₃₁ приведет к единичным значениям трех сигналов из группы s₀, … s₆ в соответствии с таблицей 3, а ошибка в одном из разрядов проверки r₀, … r₆ - к единичному значению одного сигнала из группы s₀, … s₆ с там же номером.

Сигнал об одиночной ошибке элемент 16 вырабатывает как дизъюнкцию конъюнкций прямого выходного сигнала элемента 12 с инверсным выходным сигналом элемента 13 и прямого выходного сигнала элемента 14 с инверсным выходным сигналом элемента 15.

Первая из этих конъюнкций принимает единичное логическое значение в случае нечетности только одной из контрольных сумм s₀, … s₆. Элемент 12 7ИЛИ реагирует на все случаи появления нечетных контрольных сумм, а пороговый элемент 13 с порогом 2 отсекает из них случаи нечетности более одной контрольной суммы.

Вторая конъюнкция истинна при нечетности трех контрольных сумм. Пороговый элемент 14 с порогом 3 выдает логическую единицу при появлении трех и более нечетных контрольных сумм, а пороговый элемент 15 с порогом 4 - когда таких сумм станет четыре или более.

Двойная ошибка отразится четным количеством единичных значений среди сигналов s₀, … s₆, варианты всех возможные случаев и их возможные количества представлены в таблице 4.

Продолжения таблицы 4 содержат аналогичные численные характеристики возможных вариантов тройных ошибок. Большое количество тройных ошибок, а именно 5911, сопровождаются признаками, совпадающими с признаками одиночных ошибок - равенство единице одной или трех из контрольных сумм s₀, … s₆. Такие ошибки составляют почти 65% от общего их числа 9139 и они не только идентифицируются как одиночные, 5457 из них провоцируют неадекватные исправления принятых без ошибки одиночных разрядов данных или разрядов проверки.

Четырехкратные ошибки приводят к единичным значениям у четного количества контрольных сумм. Это количество может быть нулевым, см. таблицу 6. Общее число вариантов таких случаев равно 1363,то есть 1,66% от общего числа вариантов сочетаний по 4 из 39-82251, вычисленного в результате выполнения действий: 39×38×37×36 / (4×3×2). Из чего следует, что четырехкратные ошибки могут быть обнаружены с вероятностью 0,983.

Каждая пара 11 из связанных между собой элемента 2(НЕ)-2И третьего каскада дешифратора адреса ошибки и элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ схемы коррекции состоит из шести МОП-транзисторов 18, … 23 обогащенного типа с индуцированными каналами р-типа проводимости и пяти МОП-транзисторов 24, … 28 обогащенного типа с индуцированными каналами n-типа проводимости. Истоки р-МОП-транзисторов 18, 21, 22 подключены к шине +U_П положительного напряжения питания, а истоки n-МОП-транзисторов 24, 25, 27 - к шине нулевого потенциала. Сток р-МОП-транзистора 18 соединен с истоком р-МОП-транзистора 19, сток которого вместе со стоками n-МОП-транзисторов 24, 25 и истоками МОП-транзисторов 20, 26 соединены с затворами МОП-транзисторов 22 и 28. Сток р-МОП-транзистора 22 подключен к истоку р-МОП-транзистора 23. Сток р-МОП-транзистора 21 соединен со стоком и с истоком соответственно n-МОП-транзисторов 27, 28 и с затворами р- и n-МОП-транзисторов 20 и 26. Затворы МОП-транзисторов 18, 24 и МОП-транзисторов 19, 25 соответственно соединены и являются первым и вторым входами элемента 2(НЕ)-2И, а соединенные затворы МОП-транзисторов 22, 23 и 28-первым входом X элемента ИСКЛЮЧАЮЩЕЕ-2ИЛИ. Стоки МОП-транзисторов 20, 23 и 26, 28 соединены и являются выходом элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ с функцией А1⋅А2⊕Х.

Схемотехническое решение на фиг. 8 выполняет функцию ИСКЛЮЧАЮЩЕЕ 2ИЛИ, принимающую единичные логические значения в случаях равенства единице одной и только одной из входных функций: конъюнкции А1 и А2 или повторения X.

Конъюнкцию сигналов А1 и А2, с инверсиями поступающих на соответствующие входы, выполняют МОП-транзисторы 18, 19 и 24, 25. Сигнал А1⋅А2 с их стоков поступает на затворы МОП-транзисторов 22, 28 и на истоки МОП-транзисторов 20, 26. МОП-транзисторы 21 и 27 обеспечивают необходимую для выполнения функции ИСКЛЮЧАЮЩЕЕ 2ИЛИ инверсию сигнала X.

Последовательная цепь из р-МОП-транзисторов 22 и 23 формирует на выходе А1⋅А2⊕Х высокий, соответствующий единице, логический уровень при высоком уровне сигнала на входе X и низком, соответствующим нулю, логическом уровне сигнала конъюнкции А1 и А2. Параллельная цепь из р- и n-МОП-транзисторов 20 и 26 образует ключ, пропускающий как низкий, так и высокий уровни сигнала А1⋅А2 на выход А1⋅А2⊕Х, когда на входе X низкий логический уровень. Последовательно соединенные n-МОП-транзисторы 27 и 28 подключают выход А1⋅А2⊕Х к шине нулевого потенциала, создавая низкий выходной логический уровень, при одновременно высоких уровнях сигналов А1⋅А2 и X.

Конструктивно каждая пара 11 из связанных между собой элемента 2(НЕ)-2И третьего каскада дешифратора адреса ошибки и элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ схемы коррекции выполнена в виде смежных продольными сторонами областей 29 и 30 МОП-структур р- и n-типа, поперек которых, разделяя их на области стоков-истоков соответствующих типов, проходят пять полосок 31, … 35 затворов, которые, пересекая области 29 и 30 р- и n-МОП-структур образуют области каналов р- и n-МОП-транзисторов 18, … 22 и 24, … 28 соответственно и шестая полоска 36 затвора, пересекающая область 29 МОП-структур р-типа между второй и третьей полосками 22 и 23 затворов, образуя область канала р-МОП-транзистора 23. Крайняя область истока со стороны первой полоски 31 затворов и область истоков между четвертой и пятой полосками 34 и 35 затворов в области 29 р-МОП-структур подключены к шине +U_П положительного напряжения питания, а область истоков между первой и второй полосками 31 и 32 затворов и крайняя со стороны пятой полоски 35 затворов область истока в области 30 n-МОП-структур - к шине нулевого потенциала. Область стока-истока, расположенная между второй и шестой полосками 32 и 36 затворов в области 29 р-МОП-структур, крайняя со стороны первой полоски 31 затворов область стока и область стока-истока между второй и третьей полосками 32 и 33 затворов в области 30 n-МОП-структур электрически связаны с четвертой полоской 34 затворов, а крайняя со стороны пятой полоски 35 затворов область стока в области 29 р-МОП-структур и область стока-истока между четвертой и пятой полосками 34 и 35 затворов в области 30 n-МОП-структур - с третьей полоской 33 затворов. Первая и вторая полоски 31 и 32 затворов соответственно подключены к первому и второму входам элемента 2(НЕ)-2И, а пятая и шестая полоски 35 и 36 затворов - к первому входу X элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ. Области стоков, расположенные между третьей и шестой полосками 33 и 36 затворов в области 29 р-МОП-структур и между третьей и четвертой полосками 33 и 34 затворов в области 30 n-МОП-структур, электрически связаны с выходом А1⋅А2Х элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ.

Данное конструктивное выполнение пар 11 из связанных между собой элементов 2(НЕ)-2И третьего каскада дешифратора адреса ошибки и элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ схемы коррекции обеспечивает высокую плотность размещения МОП-транзисторов за счет их сосредоточения в двух объединенных МОП-структурных областей 29 и 30, в которых электрические связи стоков и истоков МОП-транзисторов выполнены посредством их совмещения, при этом совмещенные стоки-истоки транзисторов 18-19, 20-21 не имеют контактов и, поэтому, могут быть сжаты в продольном направлении до размера, соответствующего минимальному расстоянию между полосками затворов.

Расположение области истоков, подключенные к шинам напряжения питания и нулевого потенциала, по противоположным краям областей 29 и 30 р- и n-МОП-структур при определенной ориентации смежных элементов (см. фиг. 10) позволяют совмещать эти области, что дает дополнительные возможности по повышению плотности заполнения транзисторных МОП-структур устройства.

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

Изобретение относится к области вычислительной техники. Технический результат заключается в повышении быстродействия работы устройства и устойчивости к сбоям в работе устройства. Технический результат достигается за счет предложенного выполнения функциональных узлов устройства, позволяющего уменьшить количество содержащихся в них логических элементов и длины цепей распространения логических сигналов от входов до выходов, а также уплотнить физическую КМОП-транзисторную структуру дешифратора адреса ошибки и схемы коррекции. 2 з.п. ф-лы, 10 ил., 6 табл.

1. Устройство формирования и восстановления модифицированного кода Хемминга для 32-разрядных двоичных чисел, содержащее вычислитель разрядов проверки, входы которого в количестве 32 являются входами разрядов данных устройства, а семь выходов - его выходами разрядов проверки для подключения к соответствующим входам устройства передачи или хранения данных, вычислитель адреса ошибки, входы которого в количестве 39 соединены со входами приема 32-х разрядов данных и семи разрядов проверки с выходов устройства передачи или хранения данных, дешифратор адреса ошибки, семь входов которого подключены к семи выходам вычислителя адреса ошибки, схему коррекции, состоящую из тридцати девяти элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ, первые входы которых соединены со входами приема 32-х разрядов данных и семи разрядов проверки с выходов устройства передачи или хранения данных, а вторые входы соединены с соответствующими выходами дешифратора адреса ошибки, выходы элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ являются выходами устройства для 32-х исправленных разрядов данных и семи исправленных разрядов проверки, формирователь сигналов об ошибках, семь входов которого подключены к семи выходам вычислителя адреса ошибки, а выходы являются выходами устройства для сигнала об отсутствии ошибок, сигнала об одиночной ошибке и сигнала о двойной ошибке, отличающееся тем, что вычислитель разрядов проверки состоит из тридцати одного элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, первые и вторые входы первых четырнадцати из которых в порядке возрастания номеров подключены ко входам разрядов данных соответственно с четными и нечетными номерами, следующими в порядке возрастания от 0 до 27, первые входы с 15-го по 31-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада соответственно подключены ко входам разрядов данных с номерами 11, 17, 15, 21, 29, 0, 22, 1, 23, 28, 2, 8,30, 3, 9, 7, 13, а их вторые входы - ко входам разрядов данных с номерами 14, 20, 18, 24, 30, 19, 25, 4, 26, 29, 5, 27, 31, 6, 12, 10, 16, четырнадцати элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, первые и вторые входы первых семи из которых в порядке возрастания номеров подключены к выходам элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада соответственно с нечетными и четными номерами, следующими по порядку от 1 до 14, первые входы 8-го и 10-го элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада соответственно подключены ко входам 28-го и 31-го разрядов данных, а 9-го и с 11-го по 14-й - соответственно к выходам 18-го, 23-го, 26-го, 28-го и 30-го элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, вторые входы с 8-го по 14-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада соответственно подключены к выходам 16-го, 19-го, 21-го, 24-го, 27-го, 29-го и 31-го элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, четырнадцати элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада, первые входы первых семи из которых в порядке возрастания номеров подключены к выходам 7-го и с 1-го по 6-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, а вторые входы - к выходам с 1-го по 7-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, первые входы с 8-го по 14-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада соответственно подключены к выходам 15-го, 17-го, 20-го, 22-го, 25-го, 24-го и 27-го элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, а вторые входы - к выходам с 8-го по 14-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, и с 1-го по 7-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ четвертого каскада, первые входы которых соответственно подключены к выходам с 1-го по 7-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада, вторые входы - к выходам с 8-го по 14-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада, а выходы соответственно являются выходами с нулевого по шестой разрядов проверки, вычислитель адреса ошибки состоит из тридцати одного элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, первые и вторые входы первых четырнадцати из которых в порядке возрастания номеров подключены ко входам приема разрядов данных с четными и нечетными номерами соответственно, следующими по порядку от 0 до 27, первые входы с 15-го по 31-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада соответственно подключены ко входам приема разрядов данных с номерами 11, 17, 15, 21, 29, 0, 22, 1, 23, 28, 2, 8, 30, 3, 9, 7, 13, а их вторые входы - ко входам приема разрядов данных с номерами 14, 20, 18, 24, 30, 19, 25, 4, 26, 29, 5, 27, 31, 6, 12, 10, 16, двадцати одного элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, первые и вторые входы первых семи из которых в порядке возрастания номеров подключены к выходам элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада соответственно с нечетными и четными номерами, следующими по порядку от 1 до 14, первые входы элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада с четными номерами в диапазоне от 8 до 21 соответственно подключены ко входам приема с нулевого по шестой разрядов проверки, а с нечетными номерами - соответственно ко входу приема 28-го разряда данных, к выходу 18-го элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, ко входу приема 31-го разряда данных и к выходам 23-го, 26-го, 28-го и 30-го элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, вторые входы с 8-го по 21-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада соответственно подключены к выходам 15-го, 16-го, 17-го, 19-го, 20-го, 21-го, 22-го, 24-го, 25-го, 27-го, 24-го, 29-го, 27-го, 31-го элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ первого каскада, четырнадцати элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада, первые входы первых семи из которых в порядке возрастания номеров подключены к выходам 7-го и с 1-го по 6-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, а вторые входы - к выходам с 1-го по 7-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада, первые и вторые входы с 8-го по 14-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада подключены к выходам элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ второго каскада с четными и нечетными номерами соответственно из диапазона от 8 до 21, и с 1-го по 7-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ четвертого каскада, первые входы которых соответственно подключены к выходам с 1-го по 7-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада, вторые входы -к выходам с 8-го по 14-й элементов ИСКЛЮЧАЮЩЕЕ 2ИЛИ третьего каскада, а прямые и инверсные выходы соответственно являются выходами повторений и инверсий с нулевого по шестой разрядов кода адреса ошибки, дешифратор адреса ошибки состоит из двенадцати элементов 2ИЛИ-НЕ первого каскада, первые входы которых по порядку номеров элементов соединены со входами дешифратора для повторения 0-го, инверсии 0-го, повторения 0-го, инверсии 0-го, повторения 4-го, инверсии 4-го, повторения 4-го, инверсии 4-го, повторения 1-го, инверсии 1-го, повторения 1-го, инверсии 1-го разрядов кода адреса ошибки, а вторые входы - следующими подряд парами - ко входам для повторения 2-го, инверсии 2-го, повторения 5-го, инверсии 5-го, повторения 3-го, инверсии 3-го разрядов кода адреса ошибки, двадцати элементов 2И-НЕ второго каскада, первые входы которых по порядку номеров элементов подключены к выходам элементов 2ИЛИ-НЕ первого каскада с номерами 1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 2, 1 и 9, 10, 11, 12, 11, 10, 9, вторые входы с 1-го по 4-й элементов 2И-НЕ второго каскада подключены к выходу элемента 2ИЛИ-НЕ первого каскада с номером 5, с 5-го по 7-й - с номером 6, с 8-го по 10-й - с номером 7, с 11-го по 13-й - с номером 8, вторые входы с 14-го по 17-й и с 18-го по 20-й элементов 2И-НЕ второго каскада соответственно соединены и подключены ко входам дешифратора для инверсии и повторения 6-го разряда кода адреса ошибки, тридцати девяти элементов 2(НЕ)-2И третьего каскада, первые входы которых по порядку номеров элементов подключены к выходам элементов 2И-НЕ второго каскада с номерами 4, 2, 6, 9, 3, 7, 10, 3, 7, 10, 3, 4, 13, 5, 6, 5, 13, 12, 13, 11, 9, 8, 10, 8, 2, 4, 2, 6, 9, 8, 5, 7, 2, 1, 3, 1, 5, 8, 1, а вторые входы - к выходам элементов 2И-НЕ второго каскада с номерами 15, 17, 15, 15, 17, 15, 15, 19, 16, 16, 18, 16, 16, 18, 16, 17, 20, 14, 15, 14, 20, 19, 20, 18, 19, 20, 18, 20, 16, 17, 19, 20, 14, 15, 14, 16, 14, 14, 20, выходы элементов 2(НЕ)-2И третьего каскада являются выходами адреса ошибки, формирователь сигналов об ошибках состоит из четырех 7-входовых пороговых логических элементов с порогами 1, 2, 3, 4, входы которых соответственно соединены и подключены к семи выходам вычислителя адреса ошибки, логического элемента 2(2И)-2ИЛИ, входы первого объединения 2И которого соответственно подключены к прямому и к инверсному выходам пороговых логических элементов с порогами 1 и 2, а входы второго объединения 2И - к прямому и к инверсному выходам пороговых логических элементов с порогами 3 и 4, выход элемента 2(2И)-2ИЛИ является выходом сигнала об одиночной ошибке, логического элемента 2И-2ИЛИ, входы объединения 2И которого соответственно подключены к прямому и к инверсному выходам пороговых логических элементов с порогами 2 и 3, а внешний вход объединения 2ИЛИ - к прямому выходу порогового логического элемента с порогом 4, выход элемента 2И-2ИЛИ является выходом сигнала о двойной ошибке, инверсный выход порогового логического элемента с порогом 1 является выходом сигнала об отсутствии ошибок.

2. Устройство формирования и восстановления модифицированного кода Хемминга для 32-разрядных двоичных чисел по п. 1, отличающееся тем, что каждая пара из связанных между собой элемента 2(НЕ)-2И третьего каскада дешифратора адреса ошибки и элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ схемы коррекции состоит из шести МОП-транзисторов обогащенного типа с индуцированными каналами р-типа проводимости и пяти МОП-транзисторов обогащенного типа с индуцированными каналами n-типа проводимости, истоки первого, четвертого, пятого р-МОП-транзисторов подключены к шине положительного напряжения питания, а истоки первого, второго, пятого n-МОП-транзисторов - к шине нулевого потенциала, сток первого р-МОП-транзистора соединен с истоком второго р-МОП-транзистора, сток которого вместе со стоками первого, второго n-МОП-транзисторов и истоками шестого р- и третьего и n-МОП-транзисторов соединены с затворами четвертых р- и n-МОП-транзисторов, сток четвертого р-МОП-транзистора подключен к истоку третьего МОП-транзистора аналогичного типа, сток пятого р-МОП-транзистора соединен с истоком и стоком соответственно четвертого и пятого n-МОП-транзисторов и с затворами третьих р- и n-МОП-транзисторов, затворы первых и вторых МОП-транзисторов обоих типов соответственно соединены и являются первым и вторым входами элемента 2(НЕ)-2И, а соединенные затворы пятого, шестого р-МОП- и пятого n-МОП-транзисторов - первым входом элемента ИСКЛЮЧАЮЩЕЕ-2ИЛИ, стоки третьего и шестого р-МОП- и третьего, четвертого n-МОП-транзисторов соединены и являются выходом элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ.

3. Устройство формирования и восстановления модифицированного кода Хемминга для 32-разрядных двоичных чисел по п. 2, отличающееся тем, что каждая пара из связанных между собой элемента 2(НЕ)-2И третьего каскада дешифратора адреса ошибки и элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ схемы коррекции конструктивно выполнена в виде смежных продольными сторонами областей МОП-структур р- и n-типа, поперек которых, разделяя их на области стоков-истоков соответствующих типов, проходят пять полосок затворов, которые, пересекая области р- и n-МОП-структур в порядке номеров, образуют области каналов с первых по пятые р- и n-МОП-транзисторов соответственно и шестая полоска затвора, пересекающая область МОП-структур р-типа между второй и третьей полосками затворов, образуя область канала шестого р-МОП-транзистора, крайняя область истока со стороны первой полоски затворов и область истоков между четвертой и пятой полосками затворов в области р-МОП-структур подключены к шине положительного напряжения питания, а область истоков между первой и второй полосками затворов и крайняя со стороны пятой полоски затворов область истока в области n-МОП-структур - к шине нулевого потенциала, область стока-истока, расположенная между второй и шестой полосками затворов в области р-МОП-структур, крайняя со стороны первой полоски затворов область стока и область стока-истока между второй и третьей полосками затворов в области n-МОП-структур электрически связаны с четвертой полоской затворов, а крайняя со стороны пятой полоски затворов область стока в области р-МОП-структур и область стока-истока между четвертой и пятой полосками затворов в области n-МОП-структур - с третьей полоской затворов, первая и вторая полоски затворов соответственно подключены к первому и второму входам элемента 2(НЕ)-2И, а пятая и шестая полоски затворов - к первому входу элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ, области стоков, расположенные между третьей и шестой полосками затворов в области р-МОП-структур и между третьей и четвертой полосками затворов в области n-МОП-структур, электрически связаны с выходом элемента ИСКЛЮЧАЮЩЕЕ 2ИЛИ.