ES2379239A1

ES2379239A1 - VOTING SYSTEM

Info

Publication number: ES2379239A1
Application number: ES201031492A
Authority: ES
Inventors: Jesús L�?ZARO ARROTEGUI; Armando ASTARLOA CUÉLLAR; Unai Bidarte Peraita; Aitzol ZULAGA IZAGUIRRE
Original assignee: Euskal Herriko Unibertsitatea
Current assignee: Euskal Herriko Unibertsitatea
Priority date: 2010-10-07
Filing date: 2010-10-07
Publication date: 2012-04-24
Anticipated expiration: 2030-10-07
Also published as: ES2379239B1

Abstract

Sistema votador implementado mediante un sumador aritmético, que en el caso de redundancia triple, permite además identificar una señal de entrada errónea.Voting system implemented by an arithmetic adder, which, in the case of triple redundancy, also allows the identification of an erroneous input signal.

Description

SISTEMA VOTADOR VOTING SYSTEM

CAMPO DE LA INVENCIÓN FIELD OF THE INVENTION

La presente invención se aplica al campo de los sistemas de redundancia para la corrección de errores en circuitos digitales, y más específicamente, a los votadores utilizados en dichos sistemas. The present invention applies to the field of redundancy systems for the correction of errors in digital circuits, and more specifically, to the voters used in said systems.

ANTECEDENTES DE LA INVENCIÓN BACKGROUND OF THE INVENTION

Es conocido el uso de redundancia en aplicaciones electrónicas con altos requisitos de seguridad ante fallos. Las técnicas de redundancia implican utilizar una pluralidad de circuitos independientes para obtener un solo resultado. Cada uno de los circuitos genera una señal de salida, por lo que es necesario un sistema votador (“voter” en inglés), que indica cual es el valor de salida más repetido. Dicho valor más repetido pasa a considerarse el resultado de salida del sistema de redundancia. The use of redundancy in electronic applications with high security requirements against failures is known. Redundancy techniques involve using a plurality of independent circuits to obtain a single result. Each of the circuits generates an output signal, so a voting system (“voter” in English) is required, which indicates the most repeated output value. Said more repeated value is considered the output of the redundancy system.

Por otra parte, se conocen dos formas fundamentales de realizar un circuito electrónico. On the other hand, two fundamental ways of performing an electronic circuit are known.

--: Mediante dispositivos electrónicos en los que no es posible realizar ningún cambio interno, como por ejemplo microprocesadores y circuitos integrados para aplicaciones específicas (ASIC, del inglés “Application-Specific Integrated Circuit). Through electronic devices in which it is not possible to make any internal changes, such as microprocessors and integrated circuits for specific applications (ASIC).

--: Mediante dispositivos reconfigurables (también denominados dispositivos lógicos programables), es decir, cuyas interconexiones internas y funcionalidades pueden ser modificadas una vez fabricado el dispositivo físico. Este es el caso de los arrays de puertas programables de campo (FPGA, del inglés “Field Programmable Gate Array”) y los Dispositivos Lógicos Programables Complejos (CPLD, del inglés “Complex Programmable Logic Device). Dichos circuitos reconfigurables comprenden además otros recursos fijos (o “hard”), es decir elementos que existen en la estructura de silicio desde su construcción y cuya funcionalidad queda definida por el fabricante, y no por el diseñador, como pueden ser memorias, circuitos aritméticos, microprocesadores. By means of reconfigurable devices (also called programmable logic devices), that is, whose internal interconnections and functionalities can be modified once the physical device is manufactured. This is the case of the field programmable gate arrays (FPGA) and the Complex Programmable Logic Devices (CPLD) of the Complex Programmable Logic Device. Said reconfigurable circuits also comprise other fixed resources (or "hard"), that is, elements that exist in the silicon structure since its construction and whose functionality is defined by the manufacturer, and not by the designer, such as memories, arithmetic circuits. microprocessors

Dentro del segundo grupo de circuitos electrónicos (es decir, mediante dispositivos reconfigurables), se conocen distintas técnicas relativas a la inclusión de redundancia. Por ejemplo, US 7,512,871 B1 presenta una técnica de reparación de errores una vez detectados. Por otra parte, WO 2004/077260 A2 divulga un método y aparato de creación de redundancia en dispositivos lógicos programables en el que primero se realiza un análisis del circuito para localizar puertas lógicas más sensibles a fallos, para luego aplicar sobre ellas los métodos de redundancia y protección. Finalmente, US 7,650,585 B1 presenta un modo de implementar un diseño en circuito lógico programable de modo que se reduzca el efecto de errores puntuales en el mismo. Within the second group of electronic circuits (that is, by means of reconfigurable devices), different techniques related to the inclusion of redundancy are known. For example, US 7,512,871 B1 presents an error repair technique once detected. On the other hand, WO 2004/077260 A2 discloses a method and apparatus for creating redundancy in programmable logic devices in which a circuit analysis is first performed to locate logic gates that are more sensitive to failures, then apply redundancy methods on them and protection Finally, US 7,650,585 B1 presents a way of implementing a programmable logic circuit design so as to reduce the effect of specific errors in it.

No obstante, en todos los casos anteriores, los elementos del sistema de redundancia, y en concreto los sistemas votadores, se implementan mediante elementos lógicos programables genéricos de los dispositivos reconfigurables, lo cual limita su velocidad y fiabilidad a la de dichos elementos lógicos programables. Sigue existiendo por lo tanto en el estado de la técnica la necesidad de circuitos votadores rápidos y estables que puedan ser integrados dentro de dispositivos lógicos programables. However, in all the previous cases, the elements of the redundancy system, and in particular the voting systems, are implemented by means of generic programmable logic elements of the reconfigurable devices, which limits their speed and reliability to those of said programmable logic elements. The need for fast and stable voting circuits that can be integrated into programmable logic devices still exists in the state of the art.

RESUMEN DE LA INVENCIÓN SUMMARY OF THE INVENTION

La presente invención soluciona los problemas anteriormente descritos mediante un votador que permite obtener resultados rápidos y fiables al basarse en un sumador aritmético. La invención parte de 2n-1 señales lógicas de entrada, siendo n un número entero, y obtiene como resultado al menos una salida lógica que indica el valor más repetido entre las señales lógicas de entrada. Para ello, comprende un sumador cuyas entradas son las entradas lógicas del sistema, de modo que en el bit n de salida del sumador se obtiene el resultado de la votación (siempre considerando como primer bit el bit de salida de menor peso). The present invention solves the problems described above by means of a voter that allows fast and reliable results to be obtained based on an arithmetic adder. The invention starts with 2n-1 logic input signals, where n is an integer, and results in at least one logical output that indicates the most repeated value between the logic input signals. For this, it comprises an adder whose inputs are the logical inputs of the system, so that in the output bit n of the adder the result of the vote is obtained (always considering the lowest bit output bit as the first bit).

Preferentemente, el sumador mencionado es un recurso hardware de un dispositivo lógico programable, tal como una FPGA. Es decir, no corresponde con un circuito resultante de un diseño programado sobre el dispositivo lógico, sino de un recurso físico presente en dicho dispositivo desde su fabricación. Se consigue así mejorar la fiabilidad del votador respecto a diseños realizados sobre elementos programables del dispositivo. Preferably, the adder mentioned is a hardware resource of a programmable logic device, such as an FPGA. That is, it does not correspond to a circuit resulting from a design programmed on the logical device, but from a physical resource present in said device since its manufacture. It is thus possible to improve the reliability of the voter regarding designs made on programmable elements of the device.

También preferentemente, para el caso concreto de n igual a 2, es decir, para el caso de redundancia triple (tres señales de entradas), el votador comprende una salida auxiliar de dos bits que permite, cuando se produce un error en una de las entradas lógicas del sistema, identificar dicha entrada lógica errónea. Preferentemente, dicha salida auxiliar se genera mediante dos funciones o exclusivas (es decir, dos funciones XOR, del inglés “exclusive OR”). El bit de menor peso de la salida auxiliar es la función XOR de la primera y la segunda entradas de salida, y el bit de mayor peso de la salida auxiliar es la función XOR de la segunda y la tercera entradas de salida. Also preferably, for the specific case of n equal to 2, that is, for the case of triple redundancy (three input signals), the voter comprises a two-bit auxiliary output that allows, when an error occurs in one of the logical system inputs, identify said erroneous logical input. Preferably, said auxiliary output is generated by two or exclusive functions (ie, two XOR functions, of the English "exclusive OR"). The lowest weight bit of the auxiliary output is the XOR function of the first and second output inputs, and the highest weight bit of the auxiliary output is the XOR function of the second and third output inputs.

Aún más preferentemente, dichas funciones XOR se implementan también por medio de una suma, en este caso, tomando como resultado de la función el bit de menor peso de una suma de dos señales. Al utilizar también para generar la salida auxiliar sumadores, se consigue añadir la prestación de detección de errores de forma rápida y fiable. Even more preferably, said XOR functions are also implemented by means of a sum, in this case, taking as a result of the function the bit of least weight of a sum of two signals. By also using to generate the auxiliary summers output, it is possible to add the error detection feature quickly and reliably.

Esta y otras ventajas de la invención serán aparentes a la luz de la descripción detallada de la misma. This and other advantages of the invention will be apparent in light of the detailed description thereof.

BREVE DESCRIPCIÓN DE LAS FIGURAS BRIEF DESCRIPTION OF THE FIGURES

Con objeto de ayudar a una mejor comprensión de las características del invento de acuerdo con un ejemplo preferente de realización práctica del mismo y para complementar esta descripción, se acompaña como parte integrante de la misma la siguiente figura, cuyo carácter es ilustrativo y no limitativo: In order to help a better understanding of the features of the invention according to a preferred example of practical implementation thereof and to complement this description, the following figure is attached as an integral part thereof, the character of which is illustrative and not limiting:

La figura 1 muestra un esquema del sistema votador de la invención de acuerdo con una realización preferente del mismo. Figure 1 shows a scheme of the voting system of the invention according to a preferred embodiment thereof.

DESCRIPCIÓN DETALLADA DE LA INVENCIÓN DETAILED DESCRIPTION OF THE INVENTION

En este texto, el término "comprende" y sus derivaciones (como "comprendiendo", etc.) no deben entenderse en un sentido excluyente, es decir, estos términos no deben interpretarse como excluyentes de la posibilidad de que lo que se describe y define pueda incluir más elementos, etapas, etc. In this text, the term "comprises" and its derivations (such as "understanding", etc.) should not be understood in an exclusive sense, that is, these terms should not be construed as excluding the possibility that what is described and defined can include more elements, stages, etc.

La figura 1 presenta una implementación particular del sistema votador de la invención, el cual toma como partida una pluralidad de entradas lógicas (en este caso tres entradas A B y C, aunque el sistema es igualmente válido para cualquier número de entradas igual a 2n-1, siendo n un número entero), y genera una salida lógica 1 que indica cual es la entrada lógica más repetida. Adicionalmente, el sistema tiene una salida auxiliar 2, compuesta por dos bits E0 y E1, que en caso de que una de las entradas lógicas A, B o C es errónea (es decir, su valor no coincide con el de las otras dos entradas lógicas), identifica dicha entrada errónea. En definitiva, las salidas para todas las combinaciones posibles de entrada se pueden ver en la siguiente tabla: Figure 1 presents a particular implementation of the voting system of the invention, which takes as a starting point a plurality of logical inputs (in this case three inputs AB and C, although the system is equally valid for any number of inputs equal to 2n-1 , where n is an integer), and generates a logic output 1 that indicates which is the most repeated logical input. Additionally, the system has an auxiliary output 2, composed of two bits E0 and E1, which in case one of the logic inputs A, B or C is wrong (that is, its value does not match that of the other two inputs logical), identifies the wrong entry. In short, the outputs for all possible input combinations can be seen in the following table:

ATO: B C Salida E1 E0 Error B C Departure E1 E0 Error

0 0
0 0
0 0
0 0
0 0
0 0
0 0

1 one: 0 0 0 0 0 0 0 0
1 one
1 one

0 0: 1 0 0 1 0 2 one 0 0 one 0 2

1 one
1 one: 0 1 1 1 3 0 one one one 3

0 0
0 0: 1 0 1 1 3 one 0 one one 3

1 one: 0 1 1 1 0 2 0 one one one 0 2

0 0: 1 1 1 0 1 1 one one one 0 one one

1 one
1 one
1 one
1 one: 0 0 0 0 0 0

5 donde la columna “Error” se refiere a cuál es la entrada errónea (si la hay), y por tanto corresponde con el valor numérico codificado por los bits E1 y E0. El valor “1” se refiere a la entrada A, el valor “2” a la entrada B, y el valor “3” a la entrada C. El valor “0” en dicha columna “Error” significa que todas las entradas coinciden y por lo tanto no se ha encontrado ningún error. 5 where the "Error" column refers to the wrong input (if any), and therefore corresponds to the numerical value encoded by bits E1 and E0. The value "1" refers to input A, the value "2" to input B, and the value "3" to input C. The value "0" in that column "Error" means that all inputs match and therefore no error was found.

10 Tanto la salida lógica 1 como la señal auxiliar 2 se generan mediante un sumador aritmético 3, que corresponde con un recurso fijo de un dispositivo lógico programable, es decir, no es un circuito formado por elementos programables configurados por un diseñador, sino que existe en el dispositivo lógico programable desde su fabricación. 10 Both the logic output 1 and the auxiliary signal 2 are generated by an arithmetic adder 3, which corresponds to a fixed resource of a programmable logic device, that is, it is not a circuit formed by programmable elements configured by a designer, but exists in the programmable logic device since its manufacture.

15 En concreto, la salida 1 es el segundo bit empezando por el bit menos significativo de la suma de las tres entradas A, B y C. Nótese que si el sumador tiene precisamente tres entradas, dicho segundo bit coincide con el bit de mayor peso. Sin embargo, si el sumador tiene un mayor número de entradas (y por lo tanto también de salidas), el sistema es igualmente válido, 15 Specifically, output 1 is the second bit starting with the least significant bit of the sum of the three inputs A, B and C. Note that if the adder has precisely three inputs, that second bit coincides with the bit of greatest weight . However, if the adder has a greater number of inputs (and therefore also outputs), the system is equally valid,

20 sólo que existen bits adicionales por encima del segundo que no son utilizados por el sistema votador. 20 only that there are additional bits above the second that are not used by the voting system.

En la implementación particular mostrada en la figura 1, la suma de A, B y C que corresponde con la salida 1 se realiza en dos etapas. Una primera suma parcial 4 realiza la suma de las entradas A y B, y su resultado se añade a la entrada C mediante una segunda suma parcial 6. El resultado de la suma parcial 4 (A+B), se reutiliza para la señal auxiliar 2, de modo que el bit de menor peso de dicha suma parcial 4 corresponde con el bit E0. A efectos prácticos dicho bit de menor peso de la suma parcial, realiza una función XOR. Por otra parte, una tercera suma parcial 5 realiza la suma de las entradas B y C, tomándose el bit de menor peso de dicha suma parcial 5 como bit E1 de la salida auxiliar 2. In the particular implementation shown in Figure 1, the sum of A, B and C corresponding to output 1 is done in two stages. A first partial sum 4 performs the sum of inputs A and B, and its result is added to input C by a second partial sum 6. The result of partial sum 4 (A + B) is reused for the auxiliary signal 2, so that the bit of least weight of said partial sum 4 corresponds to bit E0. For practical purposes, said bit of lower weight of the partial sum, performs an XOR function. On the other hand, a third partial sum 5 makes the sum of the inputs B and C, the bit of lesser weight of said partial sum 5 being taken as bit E1 of the auxiliary output 2.

Si ahora tomamos como ejemplo un caso típico de una FPGA que comprende dos sumadores aritméticos de 48 bits, podemos implementar el sistema votador descrito utilizando el primer sumador para realizar en paralelo la primera suma parcial 4 (A+B) y la tercera suma parcial 5 (B+C), y el segundo sumador para tomar el resultado de la primera suma parcial 4 y añadirle el valor de C mediante la tercera suma parcial 6. La realización en paralelo de dos sumas con un solo sumador es posible separando los resultados de ambas en distintos bits de salida, por ejemplo mediante replicación de señales de entrada para producir una salida de mayor orden, If we now take as an example a typical case of an FPGA comprising two 48-bit arithmetic adders, we can implement the voting system described using the first adder to perform in parallel the first partial sum 4 (A + B) and the third partial sum 5 (B + C), and the second adder to take the result of the first partial sum 4 and add the value of C by the third partial sum 6. The parallel realization of two sums with a single adder is possible by separating the results of both in different output bits, for example by replicating input signals to produce a higher order output,

o si el propio sumador permite directamente dicho modo de operación. or if the adder itself allows said mode of operation directly.

En definitiva, con el sistema descrito se consigue implementar un circuito votador en un dispositivo lógico programable que aumenta su velocidad y seguridad ante fallos al no utilizar los elementos programables del mismo. Adicionalmente, se permite detectar e identificar entradas erróneas mediante una salida auxiliar. In short, with the system described, a voter circuit is implemented in a programmable logic device that increases its speed and safety against failures by not using its programmable elements. Additionally, it is possible to detect and identify erroneous inputs through an auxiliary output.

Claims

1. Voting system comprising a number of logical inputs (A, B, C) with input values and a logical output (1) with an output value, the output value being equal to the most repeated input value in the logical inputs (A, B, C), and where the number of logical inputs (A, B, C) is equal to one less than two raised to an integer n;

characterized in that it comprises

at least one adder circuit (3) with inputs and at least the integer number n of output bits, the adder inputs (3) being the logical inputs of the system (A, B, C), and the n-simo highest bit output bit of the adder (3) the logical output (1) of the system.

2. System according to claim 1 characterized in that the adder circuit

(3) is a non-programmable hardware adder of a programmable logic device.

3.3.: Sistema según cualquiera de las reivindicaciones anteriores caracterizado porque el número entero es dos, y porque comprende además una salida auxiliar (2) de dos bits (E0, E1) que indica una entrada lógica (A, B, C) del sistema en la que se produce un error. System according to any one of the preceding claims characterized in that the integer is two, and in that it further comprises a two-bit auxiliary output (2) (E0, E1) indicating a logical input (A, B, C) of the system in which An error occurs.

4.Four.: Sistema según la reivindicación 3 caracterizado porque el bit de menos peso (E0) de la salida auxiliar (2) es una función o exclusiva de la primera entrada lógica (A) y la segunda entrada lógica (B) del sistema, y el bit de mayor peso (E1) de la salida auxiliar (2) es una función o exclusiva de la segunda entrad lógica (B) y la tercera entrada (C) lógica del sistema. System according to claim 3 characterized in that the bit of less weight (E0) of the auxiliary output (2) is a function or exclusive of the first logical input (A) and the second logical input (B) of the system, and the bit of Higher weight (E1) of the auxiliary output (2) is a function or exclusive of the second logic input (B) and the third logic input (C) of the system.

5.5.: Sistema según la reivindicación 4 caracterizado porque las funciones o exclusivas se implementan como el bit de salida de menor peso de una suma de las dos entradas lógicas. System according to claim 4, characterized in that the functions or exclusives are implemented as the lowest weight output bit of a sum of the two logic inputs.

SPANISH OFFICE OF THE PATENTS AND BRAND

Application no .: 201031492

SPAIN

Date of submission of the application: 07.10.2010

Priority Date:

REPORT ON THE STATE OF THE TECHNIQUE

51 Int. Cl.: G06F11 / 18 (2006.01)

RELEVANT DOCUMENTS

Categoría Category: 56 Documentos citados Reivindicaciones afectadas 56 Documents cited Claims Affected

X X: WO 8706037 A1 (TRIPLEX) 08.10.1987, página 9, línea 28 – página 12, línea 5; figuras. 1-5 WO 8706037 A1 (TRIPLEX) 08.10.1987, page 9, line 28 - page 12, line 5; figures. 1-5

A TO: "Triple Module Redundancy Design Techniques for Virtex FPGAs" (CARL CARMICHAEL). 06.07.2006. Xilinx, Virtex Series: Application Note XAPP197 (v1.0.1). 1-5 "Triple Module Redundancy Design Techniques for Virtex FPGAs" (CARL CARMICHAEL). 06.07.2006. Xilinx, Virtex Series: Application Note XAPP197 (v1.0.1). 1-5

A TO: US 7036059 B1 (CARMICHAEL CARL H et al.) 25.04.2006, todo el documento. 1-5 US 7036059 B1 (CARMICHAEL CARL H et al.) 25.04.2006, the whole document. 1-5

Categoría de los documentos citados X: de particular relevancia Y: de particular relevancia combinado con otro/s de la misma categoría A: refleja el estado de la técnica O: referido a divulgación no escrita P: publicado entre la fecha de prioridad y la de presentación de la solicitud E: documento anterior, pero publicado después de la fecha de presentación de la solicitud Category of the documents cited X: of particular relevance Y: of particular relevance combined with other / s of the same category A: reflects the state of the art O: refers to unwritten disclosure P: published between the priority date and the date of priority submission of the application E: previous document, but published after the date of submission of the application

El presente informe ha sido realizado • para todas las reivindicaciones • para las reivindicaciones nº: This report has been prepared • for all claims • for claims no:

Fecha de realización del informe 11.04.2012 Date of realization of the report 11.04.2012: Examinador J. Calvo Herrando Página 1/4 Examiner J. Calvo Herrando Page 1/4

REPORT OF THE STATE OF THE TECHNIQUE

Application number: 201031492

Minimum documentation searched (classification system followed by classification symbols) G06F Electronic databases consulted during the search (name of the database and, if possible, terms of

search used) INVENES, EPODOC

State of the Art Report Page 2/4

WRITTEN OPINION

Application number: 201031492

Date of Written Opinion: 11.04.2012

Statement

Novedad (Art. 6.1 LP 11/1986) Novelty (Art. 6.1 LP 11/1986): Reivindicaciones Reivindicaciones 1-5 SI NO Claims Claims 1-5 IF NOT

Actividad inventiva (Art. 8.1 LP11/1986) Inventive activity (Art. 8.1 LP11 / 1986): Reivindicaciones Reivindicaciones 1-5 SI NO Claims Claims 1-5 IF NOT

The application is considered to comply with the industrial application requirement. This requirement was evaluated during the formal and technical examination phase of the application (Article 31.2 Law 11/1986).

Opinion Base.-

This opinion has been made on the basis of the patent application as published.

State of the Art Report Page 3/4

WRITTEN OPINION

Application number: 201031492

1. Documents considered.-

The documents belonging to the state of the art taken into consideration for the realization of this opinion are listed below.

Documento Document: Número Publicación o Identificación Fecha Publicación Publication or Identification Number publication date

D01 D01: WO 8706037 A1 (TRIPLEX ) 08.10.1987 WO 8706037 A1 (TRIPLEX) 08.10.1987

D02 D02: "Triple Module Redundancy Design Techniques for Virtex FPGAs" (CARL CARMICHAEL) 06.07.2006 "Triple Module Redundancy Design Techniques for Virtex FPGAs" (CARL CARMICHAEL) 06.07.2006

D03 D03: US 7036059 B1 (CARMICHAEL CARL H et al.) 25.04.2006 US 7036059 B1 (CARMICHAEL CARL H et al.) 04.25.2006

2. Statement motivated according to articles 29.6 and 29.7 of the Regulations for the execution of Law 11/1986, of March 20, on Patents on novelty and inventive activity; quotes and explanations in support of this statement

The main object of the invention is a voting system. Document D01, which affects the inventive activity of all claims, is explained as the state of the art document closest to the object claimed, as explained below:

R1 independent claim

The voting system described by document D01 (p. 9-p. 12) comprises a number of logical inputs where the output is the value of the most repeated entry.

The difference between document D01 and the object of the present invention is that it is not specified that the voting system is implemented with at least one adder circuit, its output being the bit of greatest weight. However, this difference is considered a normal design option in the light of what is disclosed in document D02 where the use of adders in the design of voting systems is a well known technique.

Therefore, this difference is not considered to confer any element of inventive significance with respect to the known prior art. Claim R1 does not meet the inventive activity requirement set forth in Art. 8.1 LP.

R2-R5 dependent claims

The characteristic described in claim R2 is considered to be obvious to a person skilled in the art. It is not considered that it requires any inventive effort to use a non-programmable hardware adder as an adder element if the programmable logic device (FPGA) itself has this type of adders as detailed in the description of the invention itself.

As can be seen in Table 1 of document D01 (page 11), the system discloses an auxiliary output where the module where the error occurs is identified. Therefore, the object of claim R3 does not differ in any essential way from what is known in the state of the art.

The object of claims R4 and R5 comprises only embodiments and cannot be considered to involve inventive activity

Accordingly, claims R2-R5 do not imply inventive activity (Art. 8.1 LP)

State of the Art Report Page 4/4