новая папка / 4006470

4006470-Desc-ru var ctx = "/emtp"; The translation is almost like a human translation. The translation is understandable and actionable, with all critical information accurately transferred. Most parts of the text are well written using a language consistent with patent literature. The translation is understandable and actionable, with most critical information accurately transferred. Some parts of the text are well written using a language consistent with patent literature. The translation is understandable and actionable to some extent, with some critical information accurately transferred. The translation is not entirely understandable and actionable, with some critical information accurately transferred, but with significant stylistic or grammatical errors. The translation is absolutely not comprehensible or little information is accurately transferred. Please first refresh the page with "CTRL-F5". (Click on the translated text to submit corrections)

Patent Translate Powered by EPO and Google

French

German

  Albanian

Bulgarian

Croatian

Czech

Danish

Dutch

Estonian

Finnish

Greek

Hungarian

Icelandic

Italian

Latvian

Lithuanian

Macedonian

Norwegian

Polish

Portuguese

Romanian

Serbian

Slovak

Slovene

Spanish

Swedish

Turkish

  Chinese

Japanese

Korean

Russian

      PDF (only translation) PDF (original and translation)

Please help us to improve the translation quality. Your opinion on this translation: Human translation

Very good

Good

Acceptable

Rather bad

Very bad

Your reason for this translation: Overall information

Patent search

Patent examination

FAQ Help Legal notice Contact УведомлениеЭтот перевод сделан компьютером. Невозможно гарантировать, что он является ясным, точным, полным, верным или отвечает конкретным целям. Важные решения, такие как относящиеся к коммерции или финансовые решения, не должны основываться на продукте машинного перевода.

ОПИСАНИЕ ИЗОБРЕТЕНИЯ US4006470A[]

ПРЕДПОСЫЛКИ СОЗДАНИЯ ИЗОБРЕТЕНИЯ BACKGROUND OF THE INVENTION 1.

Область изобретения Field of the Invention Изобретение относится к памяти только для чтения, которая может иметь небольшой размер, и, более конкретно, к памяти только для чтения, чей блок мультиплексора может быть упрощен и чей блок матрицы ячеек памяти может быть соответственно упрощен, чтобы тем самым значительно уменьшить объем памяти. занимает весь чип. This invention relates to a read-only memory which can be constructed in a small size, and more particularly to a read-only memory whose multiplexer unit can be simplified and whose memory-cell matrix unit can accordingly be simplified to thereby greatly reduce the space occupied by the entire chip. 2.

Описание предшествующего уровня техники Description of the Prior Art Обычный блок мультиплексора функционировал только как декодер Y для входов XY и был фиксированного типа. The conventional multiplexer unit has only functioned as the Y decoder for X-Y inputs and has been of the fixed type. Настоящее изобретение направлено на предварительное упрощение блока мультиплексора с помощью технологии, которая будет описана ниже, и, таким образом, на уменьшение общего размера устройства. The present invention intends to simplify the multiplexer unit in advance by a technique which will hereinafter be described, and thereby reduce the overall size of the device. СУЩНОСТЬ ИЗОБРЕТЕНИЯ SUMMARY OF THE INVENTION Если бы постоянная память могла быть спроектирована с меньшими размерами, чем раньше, тогда стало бы возможным обеспечить в пределах обычных размеров больше пустых частей, в которых можно было бы разместить блок проверки четности или другие функциональные компоненты. If a read-only memory could be designed to smaller dimensions than before, it would then become possible to provide within the conventional dimensions more blank portions in which a parity check unit or other functional components could be accommodated. Это привело бы к обеспечению памяти только для чтения, в которой может быть размещено относительно больше функций для тех же размеров, по сравнению с памятью предшествующего уровня техники. Естественно, аналогичное постоянное запоминающее устройство можно было бы также предусмотреть в пустой части, чтобы таким образом повысить степень интенсивности на пластине. Это было бы очень эффективно для увеличения выхода продукции при производстве пластин. This would lead to the provision of a read-only memory in which relatively more functions can be accommodated for the same dimensions, as compared with the prior art memories. Naturally, a similar read-only memory could also be provided in the blank portion to thereby increase the degree of intensiveness on the wafer. This would be highly effective to enhance the yield of wafer manufacture. В соответствии с настоящим изобретением предусмотрено постоянное запоминающее устройство, которое снабжено блоком мультиплексора, имеющим по меньшей мере один объединенный столбец. According to the present invention, there is provided a read-only memory which is provided with a multiplexer unit having at least one merged column. Изобретение станет более очевидным из следующего его подробного описания в сочетании с прилагаемыми чертежами. The invention will become more fully apparent from the following detailed description thereof taken in conjunction with the accompanying drawings. КРАТКОЕ ОПИСАНИЕ РИСУНКОВ BRIEF DESCRIPTION OF THE DRAWINGS ФИГ. 1 и 2 показаны примеры обычного постоянного запоминающего устройства. FIGS. 1 and 2 show examples of the conventional read-only memory. ИНЖИР. 3 показаны детали фиг. 2. FIG. 3 shows details of FIG. 2. ИНЖИР. 4 показаны внутренние детали блока мультиплексора по фиг. 3. FIG. 4 shows internal details of the multiplexer unit of FIG. 3. ИНЖИР. 5 иллюстрирует пример мультиплексора, упрощенного согласно настоящему изобретению. FIG. 5 illustrates an example of the multiplexer simplified according to the present invention. ИНЖИР. 6 представляет собой схему конкретной схемы, модифицированной по сравнению с конструкцией, показанной на фиг. 5. FIG. 6 is a diagram of a specific circuit modified from the construction of FIG. 5. ИНЖИР. 7А показан пример таблицы истинности. FIG. 7A shows an example of a truth table. ИНЖИР. 7В показана таблица истинности по фиг. 7А в разделенной форме. FIG. 7B shows the truth table of FIG. 7A in partitioned form. ИНЖИР. 7C представляет собой новую матрицу разделения, изготовленную в соответствии с настоящим изобретением. FIG. 7C is a new partition matrix produced in accordance with the present invention. ИНЖИР. 7D иллюстрирует принцип, использованный для получения матрицы на фиг. 7С. FIG. 7D illustrates the principle used to arrive at the matrix of FIG. 7C. ИНЖИР. 8 показан пример матрицы разбиения, уменьшенной с помощью процедур, показанных на фиг. 7. FIG. 8 shows an example of a partition matrix reduced through the procedures shown in FIG. 7. ИНЖИР. 9А показан другой пример таблицы истинности. FIG. 9A shows another example of a truth table. ИНЖИР. 9B представляет собой пример неполной смежной таблицы, сформированной на основе таблицы истинности на фиг. 9А. FIG. 9B is an example of an incomplete adjacent table formed on the basis of the truth table in FIG. 9A. ИНЖИР. 10A показан пример таблицы, в которой из таблицы на фиг. 1 удален определенный ввод X. 9Б. FIG. 10A shows an example of a table which has a certain X input removed from the table of FIG. 9B. ИНЖИР. 10B показывает таблицу, в которой выполняется слияние. FIG. 10B shows the table in which merging is accomplished. ИНЖИР. 11А показан другой пример матрицы разбиения. FIG. 11A shows another example of a partition matrix. ИНЖИР. 11В показана матрица по фиг. 11А пониженный. FIG. 11B shows the matrix of FIG. 11A reduced. ИНЖИР. 12А представляет собой таблицу истинности универсального функционального генератора. FIG. 12A is a truth table for a universal function generator. ИНЖИР. 12В иллюстрирует процесс уменьшения таблицы на фиг. 12А. FIG. 12B illustrates the process of reducing the table of FIG. 12A. ИНЖИР. 12С показана таблица на фиг. 12В, уменьшенный в соответствии с настоящим изобретением. FIG. 12C shows the table of FIG. 12B reduced in accordance with the present invention. ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ ВАРИАНТОВ ВОПЛОЩЕНИЯ DESCRIPTION OF THE PREFERRED EMBODIMENTS Конструкции постоянных запоминающих устройств (ПЗУ) можно разделить на два типа, а именно тип линейного выбора, показанный на фиг. 1, и совпадающий тип выбора, показанный на фиг. 2. Тип линейного выбора представляет собой простую конструкцию, состоящую из декодера 1 и массива ячеек памяти 2, как показано, в котором, например, множество входных данных, содержащих комбинации I1-I3, проходят через декодер 1 для выбора одной из строк R1-R8 массива ячеек памяти 2, так что логическая 1 (показана черным треугольником) или логический 0, хранящиеся в упомянутой одной строке, выводятся в качестве выходного сигнала на каждой из выходных линий O1-On. Тип совпадающего выбора таков, что, как показано на фиг. 2, входы I1-I5 разделены, например, на X входов I1, I2 и Y входов I3, I4, I5. Вводы X I1, I2 вводятся в X-декодер, содержащий входной инвертор и блок буфера 4 и блок 5 селектора строк, чтобы выбрать одну из строк R1-R4. Содержимое, сохраненное в упомянутой одной строке, выводится как комбинированный сигнал выходов f0-f7 и подается на Y-декодер, который выполняет выбор строки. The constructions of read-only memories (ROM) can be classified into two types, namely, the linear selection type shown in FIG. 1 and the coincident selection type shown in FIG. 2. The linear selection type is a simple construction consisting of a decoder 1 and a memory-cell array 2 as shown, in which, for example, a plurality of inputs comprising combinations of I1 -I3 are passed through the decoder 1 to select one of rows R1 -R8 of the memory-cell array 2 so that logic 1 (shown as a black triangle) or logic 0 stored in said one row is derived as an output signal on each of the output lines O1 -On. The coincident selection type is such that, as shown in FIG. 2, inputs I1 -I5 are partitioned into X inputs I1,I2 and Y inputs I3, I4, I5, for instance. X inputs I1,I2 are entered into an X decoder comprising an input inverter and buffer unit 4 and a row selector unit 5 so as to select one of rows R1 -R4. The content stored in said one row is derived as a combination signal of outputs f0 -f7 and applied to a Y decoder which carries out row selection. Y-декодер содержит входной преобразователь и буферный блок 6 и декодер 7 строк, в который вводятся Y-входы I3, I4, I5 и множество комбинаций сигналов I3, I4 и I5 и комбинаций сигналов fi0-fi7, где i = от 1 до 4, как показано на фиг. 2, применяются к декодеру Y, при этом один из fi0-fi7 выбирается для выходов O1-O4, чтобы обеспечить вывод ПЗУ. Декодер 7 строк функционально идентичен мультиплексору и далее упоминается как мультиплексор. The Y decoder comprises an input inverter and buffer unit 6 and a row decoder 7 into which Y inputs I3,I4,I5 are entered, and a plurality of a combination of signals I3,I4 and I5 and a combination of signals fi0 -fi7, wherein i = 1 to 4 as shown in FIG. 2, are applied to the Y decoder, whereby one of fi0 -fi7 is selected for outputs O1 -O4 to provide the output of the ROM. The row decoder 7 is functionally identical with a multiplexer and is hereinafter referred to as multiplexer. Настоящее изобретение направлено на упрощение блока мультиплексора за счет использования средств, которые будут описаны ниже, и, соответственно, уменьшения размера микросхемы массива ячеек памяти, формирующего ПЗУ. Сначала будет кратко объяснена методика упрощения блока мультиплексора согласно настоящему изобретению. The present invention intends to simplify the multiplexer unit by the use of means which will hereinafter be described, and accordingly reduce the chip size of the memory-cell array forming the ROM. The technique of simplification of the multiplexer unit according to the present invention will first be explained briefly. ИНЖИР. 3 показывает только ту часть фиг. 2, который относится к одному выходу ПЗУ О1. FIG. 3 shows only that portion of FIG. 2 which is concerned with one ROM output O1. Если, как показано на фиг. 3, количество входов X равно 2, а количество входов Y равно 3, функция f этих пяти переменных (x1,x2,y1,y2,y3) может быть описана с помощью теоремы разложения Шеннона следующим образом: f (x1,x2,y1,y2,y3)=f0 (x1,x2)y1 y2 y3 + f1 (x1,x2)y1 y2 y3 + f2 (x1,x2)y1 y2 y3 + f3 (x1,x2)y1 y2 y3 + f4 (x1,x2)y1 y2 y3 + f5 (x1,x2)y1 y2 y3 + f6 (x1,x2)y1 y2 y3 + f7 (x1,x2)y1 y2 y3 If, as shown in FIG. 3, the number of X inputs is 2 and that of Y inputs is 3, the function f of these five variables (x1,x2,y1,y2,y3) may be described by the use of Shannon's expansion theorem, as follows:f(x1,x2,y1,y2,y3)=f0 (x1,x2)y1 y2 y3 + f1 (x1,x2)y1 y2 y3 + f2 (x1,x2)y1 y2 y3 + f3 (x1,x2)y1 y2 y3 + f4 (x1,x2)y1 y2 y3 + f5 (x1,x2)y1 y2 y3 + f6 (x1,x2)y1 y2 y3 + f7 (x1,x2)y1 y2 y3 Эта формула расширения может быть представлена логической схемой, показанной на фиг. 4. Из фиг. 4, который раскрывает только часть M1 блока мультиплексора, видно, что мультиплексор 7 состоит из простых логических элементов И ANDO-AND7 и логических элементов ИЛИ ИЛИ, причем количество логических элементов И равно количеству элементов, появляющихся в приведенная выше формула расширения. This expansion formula may be represented by a logic diagram as shown in FIG. 4. From FIG. 4, which discloses only a portion M1 of the multiplexer unit, it can be seen that the multiplexer 7 is made of simple AND gates ANDO-AND7 and OR gate OR, the number of the AND gates being equal to the number of terms appearing in the foregoing expansion formula. Схема на фиг. 4 может быть упрощена за счет использования методов, которые будут описаны ниже.1. Если в случае фиг. 3, например, f0 и f1 среди выходов f0-f7 матрицы ячеек G1 находятся в соотношении f0=f1=0 для всех входов X (в случае фиг.3 все комбинации x1,x2), тогда логические элементы AND ANDO и AND1 могут быть исключены на фиг. 4. Это показывает, что когда входы Y (y1,y2,y3) равны (0,0,0,) или (1,0,0,), выход равен 0 независимо от входов X.2. Если f2 = f3 для всех входов X, из следующего уравнения можно будет заменить логические элементы AND AND2 и AND3 одним вентилем AND. f2 y1 y2 y3 + f3 y1 y2 y3 = f2 y2 y3 Таким образом, входами этого нового одиночного вентиля И являются f2, y2 и y3, и его можно заменить вентилем И AND2, показанным на фиг. 5 и, когда входы Y (y1,y2,y3) равны (X,1,0), обеспечивается выход 1.3. Если f4 = f5 + f6 для всех входов X, элементы И И И4, И5 и И6 могут быть заменены двумя элементами И, показанными в следующем уравнении. +f6)y1 y2 y3 +f5 y1 y2 y3 +f6 (y1 y2 y3) =f5 y2 y3 +f6 y1 y3 The circuit of FIG. 4 may be simplified by the use of techniques which will be described below.1. If, in the case of FIG. 3, for example, f0 and f1 among the outputs f0 -f7 of the cell matrix G1 are in the relation that f0 =f1 =0 for all X inputs (in the case of FIG. 3, all combinations of x1,x2), then the AND gates ANDO and AND1 may be eliminated in FIG. 4. This shows that when Y inputs (y1,y2 ,y3) are (0,0,0,) or (1,0,0,), the output is 0 irrespective of the X inputs.2. If f2 =f3 for all X inputs, it will be possible from the following equation to replace the AND gates AND2 and AND3 by a single AND gate. f2 y1 y2 y3 + f3 y1 y2 y3 = f2 y2 y3 Thus, the inputs of this new single AND gate are f2,y2 and y3 and it may be replaced by an AND gate AND2 shown in FIG. 5 and, when Y inputs (y1,y2,y3) are (X,1,0), there is provided an output 1.3. If f4 =f5 +f6 for all X inputs, the AND gates AND4, AND5 and AND6 may be replaced by two AND gates, shown in the following equation.f4 y1 y2 y3 +f5 y1 y2 y3 +f6 y1 y2 y3 =(f5 +f6)y1 y2 y3 +f5 y1 y2 y3 +f6 (y1 y2 y3) =f5 y2 y3 +f6 y1 y3 Таким образом, входами двух логических элементов И являются (f5, y2, y3) и (f6, y1, y3) соответственно, и эти логические элементы могут быть заменены логическими элементами И И5 и И6, показанными на фиг. 5. Соответственно, в конечном результате количество логических элементов И уменьшается с 8 до 4, как показано на фиг. 5, а количество строк в матрице ячеек памяти G1 соответственно уменьшено с 8 до 4, так что ПЗУ может быть выполнено с уменьшенным вдвое пространством для матрицы ячеек G1 и части M1 мультиплексора 7. , по сравнению с конструкцией на фиг. 4. Thus, the inputs of the two AND gates are (f5,y2,y3) and (f6,y1,y3), respectively, and these gates may be replaced by AND gates AND5 and AND6 shown in FIG. 5. Accordingly, as a final result, the number of AND gates are reduced from 8 to 4 as seen in FIG. 5, and the number of rows in the memory-cell matrix G1 is correspondingly reduced from 8 to 4, so that the ROM can be made with the space for the cell matrix G1 and the portion M1 of the multiplexer 7 reduced to one-half, as compared with the construction of FIG. 4. ИНЖИР. 6 показан пример, в котором конструкция по фиг. 5 и упрощенная матрица ячеек памяти G1 образованы PNP-транзисторами с заземленными коллекторами. Подсоединение или неподключение эмиттерного вывода транзистора к столбцовой линии соответствует логическому 0 или 1, хранящемуся в матрице ячеек памяти G1, а мультиплексор M1 определяет входные выводы логических элементов И. Таким образом, метод упрощения, описанный здесь, может быть непосредственно использован для фактического изготовления и программирования ПЗУ. FIG. 6 shows an example in which the construction of FIG. 5 and the simplified memory-cell matrix G1 are formed by PNP transistors with grounded collectors. Connecting or not connecting the emitter terminal of a transistor to a column line corresponds to the logic 0 or 1 stored in the memory-cell matrix G1, and the multiplexer M1 determines the input terminals of the AND gates. In this manner, the technique of simplification described herein can be directly utilized for the actual manufacture and programming of the ROM. Подобный метод может быть также применен к матрицам ячеек памяти G2, G3, G4 и мультиплексорам M2, M3, M4 для минимизации габаритных размеров. A similar technique may likewise be applied to the memory-cell matrixes G2,G3,G4 and multiplexers M2,M3,M4 to minimize the overall dimensions. Теперь будут даны определения необходимых терминов для более подробного объяснения вышеупомянутых методов (1)-(3). Definitions of necessary terms will now be given to explain the above-mentioned techniques (1) to (3) in greater detail. ОПРЕДЕЛЕНИЕ 1. DEFINITION 1. Набор из m входных переменных может быть разбит на два подмножества, т.е. Х={х1,х2, . . . ,xs } и Y=y1,y2, . . . ,ym-s}. Матричное представление функции f означает массив из 2@m функциональных значений, выраженный матрицей из 2@s строк и 2@m-s столбцов. В этой матрице строки соответствуют 2@s различным комбинациям входов X, а столбцы — 2@m-s различным комбинациям входов Y. The set of m input variables may be partitioned into two subsets, i.e. X={x1,x2, . . . ,xs } and Y=y1,y2, . . . ,ym-s }. A partition-matrix representation of a function f means an array of 2@m functional values expressed by a matrix of 2@s rows and 2@m-s columns. In this matrix, the rows correspond to 2@s distinct combinations of the X inputs and the columns to 2@m-s distinct combinations of the Y inputs. Каждая позиция в матрице — это значение функции f, которое соответствует новой комбинации входных данных X и Y. Each position in the matrix is the value of the function f which corresponds to a new combination of X and Y inputs. Преобразование таблицы истинности для определенного логического выражения в заданную матрицу разбиения входов X и Y очень просто. Например, таблица истинности, показанная на фиг. 7A, если X={I1,I2} и Y={I3,I4,I5}, будут преобразованы в матрицу разбиения, как показано на фиг. 7Б. Хорошо известным примером является карта Карно, представляющая собой матрицу разбиения 4×4. Transformation of a truth table for a certain logic expression into a given partition matrix of X and Y inputs is very simple. For example, the truth table shown in FIG. 7A, if X={I1,I2 } and Y={I3,I4,I5 } , will be transformed into a partition matrix as shown in FIG. 7B. A well-known example is a Karnaugh map, which is a 4.times.4 partition matrix. ОПРЕДЕЛЕНИЕ 2. DEFINITION 2. Столбец Ci в матрице разбиения содержит 2@s упорядоченных элементов, каждый из которых принимает значение 0,1 или d (неважно). Значение d представляет собой обычно неиспользуемый код, и, например, когда десятичные числа от 0 до 9 закодированы в двоично-десятичные символы, шесть из шестнадцати кодов представлены d. Столбец Ci имеет адрес y i, выраженный как i=y*1, 4*2,. . . . .,y*m-s Адрес i также может быть представлен двоичным символом, если ys представлен 0, ys — 1, а отсутствующий ys — X. A column Ci in a partition matrix contains 2@s ordered elements, each of which assumes the value of 0,1 or d (don't care). The value d is a normally unused code and for example, when decimal numbers 0 to 9 are encoded into binary coded decimal characters, six of the sixteen codes are represented by d. The column Ci has a y address i, expressed as i=y*1, 4*2,. . . . .,y*m-s Address i can also be represented by a binary character if ys is represented by 0,ys by 1, and the missing ys by X. ОПРЕДЕЛЕНИЕ 3. DEFINITION 3. Если столбец Ci содержит только 0 и/или d, такой столбец Ci называется нулевым столбцом. На фиг. 7B столбец № 1 рассматривается как нулевой столбец. If a column Ci contains only 0's and/or d's, such column Ci is called a 0 column. In FIG. 7B, the column No. 1 is regarded as 0 column. ОПРЕДЕЛЕНИЕ 4. DEFINITION 4. Тогда и только тогда, когда столбцы Ci и Cj совпадают во всех местах, кроме d, говорят, что существует пересечение между Ci и Cj. Например, если Ci = [0 1 1 d 0 1 d d 0]@T и Cj = [0 d 1 1 d 1 d 0 0]@T, все соответствующие значения, кроме d, совпадают. Таким образом, в таком случае пересечение существует между Ci и Cj. If and only if columns Ci and Cj agree in every place except d, it is said that there is the intersection between Ci and Cj. For example, if Ci =[0 1 1 d 0 1 d d 0]@T and Cj =[0 d 1 1 d 1 d 0 0]@T, all the corresponding values except d agree. Thus, in such case, the intersection exists between Ci and Cj. На фиг. 7В, существует пересечение между столбцами №№ 3 и 4. In FIG. 7B, an intersection exists between columns Nos. 3 and 4. ОПРЕДЕЛЕНИЕ 5. DEFINITION 5. Тогда и только тогда, когда адреса у столбцов Ci и Cj отличаются только одним символом, говорят, что эти столбцы имеют соседние адреса. Например, на фиг. 7B среди адресов y столбцов № 3 и 4 только адрес y1 имеет разные символы 0 и 1, и, таким образом, столбцы № 3 и 4 имеют соседние адреса. If and only if the y addresses of columns Ci and Cj differ only in one character, it is said that these columns have neighboring addresses. For example, in FIG. 7B, among the y addresses of columns Nos. 3 and 4, only the y1 address has different characters 0 and 1 and thus, columns Nos. 3 and 4 have neighboring addresses. ОПРЕДЕЛЕНИЕ 6. DEFINITION 6. Тогда и только тогда, когда существует пересечение между двумя столбцами Ci и Cj, имеющими соседние адреса, столбцы Ci и Cj совместимы. Например, на фиг. 7B столбцы № 3 и 4 совместимы, поскольку они имеют соседние адреса и имеют пересечение между ними, как отмечено выше. If and only if an intersection exists between two columns Ci and Cj having neighboring addresses, the columns Ci and Cj are compatible. For example, in FIG. 7B, columns Nos. 3 and 4 are compatible because they have neighboring addresses and have the intersection therebetween as noted above. ОПРЕДЕЛЕНИЕ 7. DEFINITION 7. В столбцах Ci,Cj, имеющих соседние адреса, если все элементы Cj равны 1, а соответствующие элементы Ci всегда отличны от 0, то говорят, что Ci доминирует над Cj, и это отношение записывается как Ci > Cj. Например, когда Ci = [1 0 1 1 d]@T и Cj = [0 0 d 1 1]@T, элементы Ci, соответствующие элементам 1 Cj, равны 1 и d, и, таким образом, Ci > Cj. На фиг. 7B, если столбцы № 3 и 4 соответствуют Ci и Cj соответственно, столбец № 3 доминирует над столбцом № 4, поскольку элементы столбца № 3, соответствующие элементам 1 столбца № 4, равны 1. Кроме того, в этом случае, если столбцы № 3 и 4 соответствуют Cj и Ci соответственно, элементы столбца № 4, соответствующие элементам 1 столбца № 3, равны 1, и, таким образом, столбец № 4 считается доминирующим. столбец №3. In columns Ci,Cj having neighboring addresses, if all elements of Cj are 1 while the corresponding elements of Ci are always other than 0, then Ci is said to dominate Cj, and this relation is written as Ci > Cj. For example, when Ci =[1 0 1 1 d]@T and Cj =[0 0 d 1 1]@T, the elements of Ci corresponding to the elements 1 of Cj are 1 and d and thus, Ci > Cj. In FIG. 7B, if columns Nos. 3 and 4 correspond to Ci and Cj, respectively, column No. 3 dominates column No. 4 because the elements of column No. 3 corresponding to the elements 1 of column No. 4 are 1. Also, in this case, if columns Nos. 3 and 4 correspond to Cj and Ci respectively, the elements of column No. 4 corresponding to the elements 1 of column No. 3 are 1 and thus, column No. 4 is said to dominate column No. 3. Следствие 1. Необходимые и достаточные условия совместимости двух столбцов Ci и Cj заключаются в том, что Ci > Cj и Cj > Ci одновременно. COROLLARY 1 The necessary and sufficient conditions for two columns Ci and Cj to be compatible are that Ci > Cj and Cj > Ci at one time. ОПРЕДЕЛЕНИЕ 8. DEFINITION 8. Произведение Ci и Cj (записывается как Ci Cj) определяется следующим образом: The product of Ci and Cj (written as Ci Cj) is defined as follows: Если Ci и Cj имеют одинаковую длину и если оба Ci и Cj содержат элемент d, их произведение равно d; если любой из Ci и Cj содержит 0, их произведение равно 0; а в остальных случаях произведение равно 1. Например, если Ci = (10d1d1) и Cj = (10d100), произведение Ci Cj = (10d100). If Ci and Cj are of the same length and if both of Ci and Cj contain the element d, the product thereof is d; if either of Ci and Cj contains 0, the product thereof is 0; and in the other cases, the product is 1. For example, if Ci =(10d1d1) and Cj =(10d100), the product Ci Cj =(10d100). ОПРЕДЕЛЕНИЕ 9. DEFINITION 9. Если Ci и Cj имеют соседние адреса, Ci и Cj можно объединить. Объединенный столбец (записанный как Ci.Cj) является произведением Ci и Cj, а его адрес представляет собой логическую сумму адресов y, i и j. Например, если Ci = [1 0 1 0]@T и его адрес i=y1 y2 y3 и если Cj = [1 d 1 0]@T и его адрес j=y1 y2 y3, то Ci и Cj можно объединить . Объединенный столбец представлен Ci Cj =[1 0 1 0], а его адрес i+j=y1 y2 y3 +y1 y2 y3 =y2 y3. На фиг. 7В столбцы №№ 3 и 4 могут быть объединены. If Ci and Cj have neighboring addresses, Ci and Cj can be merged. The merged column (written as Ci.Cj) is the product of Ci and Cj and its address is the logical sum of the y addresses, i and j. For example, if Ci =[1 0 1 0]@T and its address i=y1 y2 y3 and if Cj =[1 d 1 0]@T and its address j=y1 y2 y3, then Ci and Cj can be merged. The merged column is represented by Ci Cj =[1 0 1 0]and its address by i+j=y1 y2 y3 +y1 y2 y3 =y2 y3. In FIG. 7B, columns Nos. 3 and 4 can be merged. ОПРЕДЕЛЕНИЕ 10. DEFINITION 10. Фундаментальный продукт — это логическое произведение различных входных элементов, выход которых равен 1. Например, на фиг. 7A, фундаментальный продукт строки, выход f которой равен 1, скажем, седьмой строки, представлен как I1 I2 I3 I4 I5. Таким образом, когда матрица разбиения задана в соответствии с приведенными выше определениями, количество столбцов может быть уменьшено с помощью следующего метода. Шаг 1: Удалите 0 столбцов. Шаг 2: Объедините все возможные пары оставшихся столбцов. Шаг 3. Повторяйте шаги 1 и 2 до тех пор, пока столбцы не будут объединены. Шаг 4. Выберите наименьшее количество столбцов, содержащих все основные продукты. A fundamental product is the logical product of various input elements whose output is 1. For example, in FIG. 7A, the fundamental product of a row whose output f is 1, say, the seventh row, is represented by I1 I2 I3 I4 I5. Thus, when a partition matrix is given in accordance with the above definitions, the number of the columns may be reduced by the following technique. Step 1: Eliminate 0 columns. Step 2: Merge all possible pairs of the remaining columns. Step 3: Iterate steps 1 and 2 until no more columns can be merged. Step 4: Choose the least number of columns that include all the fundamental products. Эти шаги являются обобщением вышеупомянутых методов (1), (2) и (3). These steps are the generalization of the aforementioned techniques (1), (2) and (3). ФИГ. 7B, C и D иллюстрируют процесс, во время которого таблица истинности по фиг. 7А уменьшен, как показано на ФИГ. 8 с использованием предыдущих шагов 1-4. FIGS. 7B, C and D illustrate the process during which the truth table of FIG. 7A is reduced as shown in FIG. 8 by the use of the foregoing steps 1-4. Более конкретно, если входные данные I1-I5 в таблице истинности на фиг. 7A разбиваются по желанию, например, на x=2 и y=3, и если I1=x1, I2=x2, I3=y1, I4=y2 и I5=y3, то матрица разбиения для фиг. 7 Таблица может быть записана так, как показано на фиг. 7Б. Адрес y каждого столбца переписывается в виде строки и добавляется в левое поле на фиг. 7Д. Самый верхний блок на фиг. 7D показаны основные продукты, представленные в двоичной системе и переписанные в виде столбцов. Впоследствии на фиг. 7В выбираются строки I1, I2 и столбцы I3, I4, I5, в которых матричный элемент равен 1, а группы основных элементов произведения, в которых элементы I1-I5 идентичны, выбираются из столбцов на фиг. . 7Д. Кроме того, когда те y адресуют y1, y2, y3, с которыми y обращается на фиг. 7B совпадают, выбраны на фиг. 7 определены строки и столбцы, и точки пересечения между ними отмечены знаком X. More specifically, if the inputs I1 -I5 in the truth table of FIG. 7A are partitioned as desired, for example, into x=2 and y=3, and if I1 =x1, I2 =x2, I3 =y1, I4 =y2 and I5 =y3, then a partition matrix for the FIG. 7A table may be written as shown in FIG. 7B. The y address of each column is rewritten into the form of row and added to the left box of FIG. 7D. The uppermost box in FIG. 7D shows the fundamental products as represented by the binary system and rewritten in the form of columns. Subsequently, in FIG. 7B, the rows I1,I2 and the columns I3,I4,I5 in which the matrix element is 1 are chosen, and the groups of fundamental product elements in which the elements of I1 -I5 are identical are chosen from among the columns in FIG. 7D. Also, when those y addresses y1, y2,y3 with which the y addresses in FIG. 7B are coincident are chosen in FIG. 7, the rows and columns are determined and the points of intersection therebetween are thus marked with X. Например, на фиг. 7В элемент матрицы равен 1 на пересечении между строкой № 1 и столбцом № 3, и в этой строке и столбце I1 - I5 = 00010, а столбец, в котором это дает фундаментальный продукт, является столбцом № 1 на фиг. 7Д. Кроме того, адреса y y1, y2, y3 в этом случае равны 010, и, таким образом, адреса y в строке № 3 на фиг. 7D соответствуют этому. Следовательно, пересечение между строкой № 3 и столбцом № 1 на фиг. 7D отмечен знаком X. Кроме того, пересечение между строкой № 3 и столбцом № 3 на фиг. 7B равно 1, и в этой строке I1=x1=0 и I2=x2=1, а в этом столбце I3=y1=0, I4=y2=1 и I5=y3=0. Таким образом, I1-I5=01010. For example, in FIG. 7B, the matrix element is 1 at the intersection between the row No. 1 and the column No. 3, and in this row and column, I1 -I5 =00010, and the column in which this provides the fundamental product is the column No. 1 in FIG. 7D. Also, the y addresses y1,y2,y3 in this case are 010 and so, the y addresses in the row No. 3 in FIG. 7D correspond thereto. Therefore, the intersection between row No. 3 and column No. 1 in FIG. 7D is marked with X. Also, the intersection between row No. 3 and column No. 3 in FIG. 7B is 1 and in that row, I1 =x1 =0 and I2 =x2 =1 and in that column, I3 =y1 =0, I4 =y2 =1 and I5 =y3 =0. Thus, I1 -I5 =01010. Основной продукт, в котором элементы идентичны, находится в столбце № 2 на фиг. 7Д. Кроме того, в этом случае адреса у I3 =y1 =0, I4 =y2 =1 и I5 =y3 =0 равны 010 и, следовательно, им соответствует строка № 3, а пересечение между строкой № 3 и столбцом № 2 отмечен знаком X. Знаки X наносятся с помощью тех же процедур, чтобы обеспечить показанные условия. Далее, на фиг. 7D, метка X предусмотрена в каждой точке пересечения строк, чьи адреса y все еще не отмечены знаком X. Эти строки, отмеченные знаком X, соответствуют вышеупомянутым столбцам O и, следовательно, исключены. Это соответствует шагу 1, описанному ранее. В данном случае строки №№ 1 и 2 отмечены X и удалены. В дальнейшем оставшиеся строки подвергаются объединению, которое соответствует ранее описанному шагу 2, и элементы объединяемых строк дополнительно записываются в последнюю адресную строку y (строка № 8) и далее. The fundamental product in which the elements are identical is found in column No. 2 of FIG. 7D. Also, in this case, the y addresses I3 =y1 =0, I4 =y2 =1 and I5 =y3 =0 are 010 and so, row No. 3 corresponds thereto, and the intersection between row No. 3 and column No. 2 is marked with X. The marks X are provided through the same procedures to bring about the conditions shown. Next, in FIG. 7D, a mark X is provided at every point of intersection on the rows having their y addresses still unmarked with X. These rows marked with X correspond to the aforesaid O columns and are therefore eliminated. This corresponds to the step 1 previously described. In the present instance, the rows Nos. 1 and 2 are marked with X and eliminated. Subsequently, the remaining rows are subjected to the merging which corresponds to the step 2 previously described, and the elements of the merged rows are additionally written in the last y address row (row No. 8) and on. Более конкретно, адреса y строк № 3 и 4 являются соседними адресами и, следовательно, объединены, а новая объединенная строка представлена как X, 1, 0 и записана в строке № 9. Точно так же строки № 3 и 7 можно объединить и представить как 0, 1, X, что записывается в строке № 10. Таким же образом строки № 4 и 8 можно объединить и представить как 1, 1, X, строки № 5 и 7 как 0, X, 1, строки № 5 и 6 как X, 0, 1, строки №№ 7 и 8 как X, 1, 1, и они записаны в строках №№ 11, 12, 13, 14 и 15 соответственно. Эти новые адреса y, полученные в результате слияния, перезаписываются в виде столбцов, как показано на фиг. 7С. Адреса x также переписаны с фиг. 7В в ФИГ. 7С. На этом этапе вводится новая матрица разбиения с использованием определений 8 и 9, описанных выше. Более конкретно, например, матричный элемент на пересечении между строкой №1 и столбцом №1 может быть получен следующим образом. Y-адрес X, 1, 0 столбца № 1 получился в результате слияния у-адресов столбцов № 3 и 4 на фиг. 7Б, при этом элементы матрицы адреса x строки №1 равны 1 и 1 соответственно, а их логическое произведение равно 1. More specifically, the y addresses of the rows Nos. 3 and 4 are neighboring addresses and therefore merged, and the new merged row is represented as X, 1, 0 and written in the row No. 9. Likewise, the rows Nos. 3 and 7 may be merged and represented as 0, 1, X, which is written in the row No. 10. In the same manner, the rows Nos. 4 and 8 can be merged and represented as 1, 1, X, the rows Nos. 5 and 7 as 0, X, 1, the rows Nos. 5 and 6 as X, 0, 1, the rows Nos. 7 and 8 as X, 1, 1, and these are written in the rows Nos. 11, 12, 13, 14 and 15, respectively. These new y addresses resulting from the merging are rewritten in the form of columns as shown in FIG. 7C. The x addresses are also rewritten from FIG. 7B into FIG. 7C. At this point, a new partition matrix is introduced by the use of the definitions 8 and 9 described above. More specifically, for example, the matrix element at the intersection between the row No. 1 and the column No. 1 may be obtained in the following manner. The y address X, 1, 0 of the column No. 1 has resulted from the merging of the y addresses of the columns Nos. 3 and 4 in FIG. 7B, while the matrix elements of the x address of the row No. 1 are 1 and 1, respectively, and their logical product is 1. Следовательно, это логическое произведение как вновь созданный матричный элемент записывается на пересечение строки № 1 и столбца № 1 на фиг. 7С. Элементы матрицы по адресу y того же столбца №1 и по адресу y на пересечении строки №2 и столбца №2 соответствуют 0 и d по адресу x строки №2 в ее пересечение со столбцами адреса y № 3 и 4 на фиг. 7B, и поскольку логическое произведение 0 и d равно 0, 0 помещается на пересечении между строкой № 2 и столбцом № 1 на фиг. 7С. Таким образом, все матричные элементы могут быть получены, как показано. Вышеупомянутый этап 1 снова выполняется с использованием этой новой матрицы разделения (фиг. 7C) и новых объединенных адресов y (блок d2 на фиг. 7D). Следует отметить, однако, что шаг 1 выполняется для обоих случаев, когда X равно 0 и где X равно 1, и точка пересечения, подпадающая под оба из них, отмечена X. Например, шаг 1 выполняется сначала для случая, когда X=0. Therefore, this logical product as a newly produced matrix element is written into the intersection between the row No. 1 and the column No. 1 in FIG. 7C. The matrix elements at the y address of the same column No. 1 and the y address at the intersection between the row No. 2 and the column No. 2 correspond to 0 and d at the x address of the row No. 2 at its intersection with the y address columns Nos. 3 and 4 in FIG. 7B, and since the logical product of 0 and d is 0, 0 is placed at the intersection between the row No. 2 and the column No. 1 in FIG. 7C. In this manner, all matrix elements may be obtained as shown. The aforementioned step 1 is again carried out by using this new partition matrix (FIG. 7C) and the new merged y addresses (box d2 in FIG. 7D). It should be noted, however, that step 1 is carried out for both cases where X is 0 and where X is 1, and the point of intersection falling under both of them is marked with X. For example, step 1 is first carried out for the case where X=0. Адрес X, 1, 0 столбца № 1 на фиг. 7C становится равным 0, 1, 0, а матричный элемент на пересечении с адресом x 0, 0 строки № 1 равен 1, так что его основной продукт 00010 можно найти в столбце № 1 на фиг. 7Д. Поэтому пересечение строки № 9 и столбца № 1 в клетке d2 отмечено знаком X. The y address X, 1, 0 of the column No. 1 in FIG. 7C becomes 0, 1, 0 and the matrix element at the intersection with the x address 0, 0 of the row No. 1 is 1, so that the fundamental product 00010 thereof can be found in the column No. 1 in FIG. 7D. Therefore, the intersection between the row No. 9 and the column No. 1 in the box d2 is marked with X. Кроме того, когда X=1, I1-I5 на фиг. 7C имеют значение 00110, и, таким образом, их основной продукт соответствует произведению в столбце 3 на фиг. 7D, а пересечение между строкой № 9 и столбцом № 3 отмечено знаком X. Поскольку элемент на пересеч