# US 2004/0073586 A1 · Method and relative circuit for incrementing, decrementing or two's complementing a bit string

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0073586 A1
- Document ID: US20040073586A1
- Status: Published application
- Kind: A1
- Application number: 10/651,075
- Filed: 2003-08-28
- Published: 2004-04-15
- Earliest claimed: 2002-08-30
- Assignees: STMicroelectronics S.r.I.
- Inventors: Daniele Lo Iacono
- Web page: https://patentgrep.com/patent/US20040073586A1

## CPC

- G06F 7/5055: {in which one operand is a constant, i.e. incrementers or decrementers}
- G06F 7/48: using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F 7/49921: {Saturation, i.e. clipping the result to a minimum or maximum value}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for incrementing, decrementing or two's complementing a first string of bits includes generating an auxiliary string of bits as a function of the first string, and logically combining the auxiliary string with the first string to generate a corresponding output string. A least significant bit of the auxiliary string is independent from the bits of the first string, and any other bit of the auxiliary string. The method is particularly convenient for generating an overflow flag when the number to be output exceeds the representation interval. An overflow flag is generated by logically combining the most significant bits of the first and auxiliary strings.

## Claims

### Claim 1

A method for incrementing, decrementing or two's complementing a N bit string (K), comprising
generating an auxiliary string (M; {overscore (M)}) of N bits, in function of said string (K), whose least significant bit is independent from said string (K) and any other bit (MI; {overscore (M1)}), starting from the second least significant bit (M1; {overscore (M1)}) up to the most significant bit (MN-1; {overscore (MN-1)}), is a logic combination of a corresponding bit (KI-1; {overscore (K1-1)}) of said first string (K) or of a negated replica thereof ({overscore (K)}), starting from the least significant bit (K0; {overscore (K0)}) up to the second most significant bit (KN-2; {overscore (KN-2)}), and of the bits of said first string (K) or of the negated replica thereof ({overscore (K)}) less significant than said corresponding bit (K0, . . . , KI-2; {overscore (K0)}, . . . , {overscore (K1-2)})
generating an output string (Y) as a logic combination of said auxiliary string (M; {overscore (M)}) and of said first string (K).

### Claim 2 (depends on 1)

The method of claim 1, wherein the least significant bit of said auxiliary string (M) is always null and any other bit (MI), starting from the second least significant bit (MN-1) up to the most significant bit (MN-1), is the logic OR of a corresponding bit of said first string ({overscore (K101)}) or of a negated replica thereof ({overscore (K1-1)}) and of said bits less significant than said corresponding bit (K0, . . . , KI-2; {overscore (K0)}, . . . {overscore (K1-2)}).

### Claim 3 (depends on 1)

The method of claim 1, wherein the least significant bit of said auxiliary string ({overscore (M)}) is always 1 and any other bit ({overscore (1)}), starting from the second least significant bit ({overscore (1)}) up to the most significant bit ({overscore (MN-1)}), is the logic AND of a corresponding bit of said first string (KI-1) or of a negated replica thereof ({overscore (K1-1)}) and of said bits less significant than said corresponding bit (K0, . . . , KI-2; {overscore (K)}0, . . . , {overscore (K1-2)}).

### Claim 4 (depends on 1)

The method of claim 1, further comprising generating an overflow flag (OF) as a logic combination among the most significant bits of said auxiliary string (MN-1; {overscore (MN-1)}) and of said first string (KN-1).

### Claim 5 (depends on 2)

The method of claim 2 for two's complementing said first string (K), wherein
said other bit of the auxiliary string (MI) is obtained by ORing the immediately less significant bit (MI-1) of said auxiliary string (M) and a corresponding bit of said first string (KI-1);
said output string (Y) is obtained as XOR of said string (K) to be complemented and of said auxiliary string (M).

### Claim 6 (depends on 3)

The method of claim 3 for two's complementing said first string (K), wherein
said other bit of the auxiliary string ({overscore (M1)}) is obtained by ANDing the immediately less significant bit ({overscore (M1-1)}) of said auxiliary string ({overscore (M)}) and a corresponding bit of said first string (KI-1);
said output string (Y) is obtained as negated XOR of said string (K) to be complemented and of said auxiliary string ({overscore (M)}).

### Claim 7 (depends on 2)

The method of claim 2 for decrementing said first string (K), wherein
said other bit of the auxiliary string (MI) is obtained by ORing the immediately less significant bit (MI-1) of said auxiliary string (M) and a corresponding bit of said first string (KI-1);
said output string (Y) is obtained as negated XOR of said first string (K) and of said auxiliary string (M).

### Claim 8 (depends on 3)

The method of claim 3 for decrementing said first string (K), wherein
said other bit of the auxiliary string ({overscore (M1)}) is obtained by ANDing the immediately less significant bit ({overscore (M1-1)}) of said auxiliary string ({overscore (M)}) and a corresponding bit of said first string (KI-1);
said output string (Y) is obtained as XOR of said first string (K) and of said auxiliary string ({overscore (M)}).

### Claim 9 (depends on 2)

The method of claim 2 for incrementing said first string (K), wherein said other bit of the auxiliary string (MI) is obtained by ORing the immediately less significant bit (MI-1) of said auxiliary string (M) and the negated replica ({overscore (K1-1)}) of a corresponding bit of said first string (KI-1)
said output string (Y) is obtained by XORing said auxiliary string (M) and a negated replica of said first string (K).

### Claim 10 (depends on 3)

The method of claim 3 for incrementing said first string (K), wherein said other bit of the auxiliary string ({overscore (M1)}) is obtained by ANDing the immediately less significant bit ({overscore (M1-1)}) of said auxiliary string ({overscore (M)}) and a corresponding bit of said first string (KI-1);
said output string (Y) is obtained as negated XOR of said first string (K) and of said auxiliary string ({overscore (M)}).

### Claim 11 (depends on 2, 4)

The method of claims 2 and 4 for two's complementing or decrementing said first string (K), wherein said overflow flag (OF) is generated by ANDing the most significant bit of said first string (KN-1) and a negated replica of the most significant bit of said auxiliary string (MN-1).

### Claim 12 (depends on 3, 4)

The method of claims 3 and 4 for two's complementing or decrementing said first string (K), wherein said overflow flag (OF) is generated by ANDing the most significant bit of said first string (KN-1) and the most significant bit of said auxiliary string ({overscore (MN-1)}).

### Claim 13 (depends on 2, 4)

The method of claims 2 and 4 for incrementing said first string (K), wherein said overflow flag (OF) is generated by ANDing the negated replicas of the most significant bits of said first string (KN-1) and of said auxiliary string (MN-1).

### Claim 14 (depends on 3, 4)

The method of claims 3 and 4 for incrementing said first string (K), wherein said overflow flag (OF) is generated by ANDing the negated replica of the most significant bit of said first string (KN-1) and the most significant bit of said auxiliary string ({overscore (MN-1)}).

### Claim 15 (depends on 11)

The method of claim 11 for two's complementing said first string (K) with correction of the output in case of overflow, wherein
said other bit of the auxiliary string (MI) is obtained by ORing the immediately less significant bit (MI-1) of said auxiliary string (M) and a corresponding bit of said string (KI-1);
the most significant bit of said output string (Y) is obtained by NORing the most significant bit of said first string (KN-1) and the negated replica of the most significant bit of said auxiliary string (MN-1),
any other bit of said output string (Y) is obtained by ORing the overflow flag (OF) and the logic XOR between corresponding bits of said first string (K) and of said auxiliary string (M).

### Claim 16 (depends on 11)

The method of claim 11 for two's complementing said first string (K) with correction of the output in case of overflow, wherein
said other bit of the auxiliary string (MI) is obtained by ORing the immediately less significant bit (MI-1) of said auxiliary string (M) and a corresponding bit of said string (KI-1);
the most significant bit of said output string (Y) is obtained by NORing the most significant bit of said first string (KN-1) and the negated replica of the most significant bit of said auxiliary string (MN-1)
any other bit of said output string (Y) is obtained by XORing the overflow flag (OF) and the logic XOR between corresponding bits of said first string (K) and of said auxiliary string (M).

### Claim 17 (depends on 11)

The method of claim 11 for decrementing said first string (K) with correction of the output in case of overflow, wherein
said other bit of the auxiliary string (MI) is obtained by ORing the immediately less significant bit (MI-1) of said auxiliary string (M) and a corresponding bit of said string (KI-1);
the most significant bit of said output string (Y) is obtained by ORing the most significant bit of said first string (KN-1) and the negated replica of the most significant bit of said auxiliary string (MN-1) ;
any other bit of said output string (Y) is obtained by XORing the negated replica of the overflow flag (OF) and the logic XOR between corresponding bits of said first string (K) and of said auxiliary string (M).

### Claim 18 (depends on 13)

The method of claim 13 for incrementing said first string (K) with correction of the output in case of overflow, wherein
said other bit of the auxiliary string (MI) is obtained by ORing the immediately less significant bit (MI-1) of said auxiliary string (M) and the negated replica ({overscore (K1-1)}) of a corresponding bit of said string (KI-1) ;
the most significant bit of said output string (Y) is obtained by NORing the most significant bit of said first string (KN-1) and the negated replica of the most significant bit of said auxiliary string (MN-1);
any other bit of said output string (Y) is obtained by ORing the overflow flag (OF) and the logic XOR between corresponding bits of said first string (K) and of said auxiliary string (M).

### Claim 19

A circuit for incrementing, decrementing or two's complementing a N bit string (K), comprising an auxiliary circuit (OR MASK; AND MASK) generating an auxiliary string (M; {overscore (M1)}) of N bits, in function of said string (K), whose least significant bit is independent from said string (K) and any other bit (MI; {overscore (M1)}), starting from the second least significant bit (M1; {overscore (M1)}) up to the most significant bit (MN-1; MN-1), is a logic combination of a corresponding bit (KI-1; {overscore (K1-1)}) of said first string (K) or of a negated replica thereof ({overscore (K)}), starting from the least significant bit (K0; {overscore (K0)}) up to the second most significant bit (KN-2; {overscore (KN-2)}), and of the bits of said first string (K) or of the negated replica thereof ({overscore (K)}) less significant than said corresponding bit (K0, . . . , KI-2; {overscore (K0)}, . . . , {overscore (K1-2)});
logic circuit means generating an output string (Y) as a logic combination of said auxiliary string (M; {overscore (M)}) and of said first string (K).

### Claim 20 (depends on 19)

The circuit of claim 19, wherein said auxiliary circuit (OR MASK) generates the auxiliary string (M) with the least significant bit always null, the second least significant bit of said auxiliary string (M) as replica of the least significant bit of the first string (K0) or as negated replica thereof ({overscore (K0)}), and further comprises
N-2 OR gates each generating a respective bit of said auxiliary string (M), starting from the third least significant bit (M2) up to the most significant bit (MN-1) by ORing a corresponding bit (KI-1; {overscore (K1-1)}) of said first string (K) or of a negated replica thereof ({overscore (K)}), starting from the least significant bit (K0; {overscore (K0)}) up to the second most significant bit (KN-2; {overscore (KN-2)}), and the bits of said first string (K) or of the negated replica thereof ({overscore (K)}) less significant than said corresponding bit (K0, . . . , KI-2; {overscore (K0)}, . . . , {overscore (K1-2)}).

### Claim 21 (depends on 19)

The circuit of claim 19, wherein said auxiliary circuit (OR MASK) generates the auxiliary string (M) with the least significant bit always null, the second least significant bit of said auxiliary string (M) as replica of the least significant bit of the first string (K0) or as negated replica thereof ({overscore (K0)}), and further comprises
N-2 OR gates each generating a respective bit of said auxiliary string (M), starting from the third least significant bit (M2) up to the most significant bit (MN-1), disposed in a cascade of pairs of logic gates, the gates of a first pair generating the third and fourth least significant bits of said auxiliary string (M2, M3) by ORing the two (K0, K1) and the three least significant bits (K0, K1, K2), respectively, of said first string (K) or of the negated replica thereof ({overscore (K)}), each pair of OR gates being input with a respective pair of consecutive bits first (KI-2) and second (KI-1) of said first string (K) or of the negated replica thereof ({overscore (K)}) and the most significant bit of said auxiliary string generated by the pair of gates that precedes in the cascade (MI-2), and generating two consecutive bits of said auxiliary string (MI-1, MI) by ORing said most significant bit generated by the pair of gates that precedes in the cascade (MI-2) and respectively said first bit (KI-2) and both said bits first (KI-2) and second (KI-1) of said respective pair of bits.

### Claim 22 (depends on 19)

The circuit of claim 19, wherein said auxiliary circuit (OR MASK) generates the auxiliary string (M) with the least significant bit always null, the second least significant bit of said auxiliary string (M) as replica of the least significant bit of the first string (K0) or as negated replica thereof ({overscore (K0)}), and further comprises
a cascade of N-2 OR gates input with a respective bit of said first string (K) or of the negated replica thereof in order starting from the second least significant bit (K1) up to the second most significant bit (KN-2), each gate generating a respective bit of said auxiliary string (M), starting from the third least significant bit (M2) up to the most significant bit (MN-1), as logic OR of the respective bit of said first string (K) or of the negated replica thereof and of the bit of the auxiliary string (M) generated by the OR gate that precedes in the cascade.

### Claim 23 (depends on 19)

The circuit of claim 19, wherein said auxiliary circuit (AND MASK) generates the auxiliary string ({overscore (M)}) with the least significant bit always equal to 1, the second least significant bit of said auxiliary string ({overscore (M)}) as replica of the least significant bit of the first string (K0) or as negated replica thereof (K0) and further comprises
a cascade of N-2 AND gates input with a respective bit of said first string (K) or of the negated replica thereof in order starting from the second least significant bit (K1) up to the second most significant bit (KN-2), each gate generating a respective bit of said auxiliary string ({overscore (M)}), starting from the third least significant bit ({overscore (M2)}) up to the most significant bit ({overscore (MN-1)}), by ANDing the respective bit of said first string (K) or of a negated replica thereof and the bit of the auxiliary string ({overscore (M)}) generated by the AND gate that precedes in the cascade.

### Claim 24 (depends on 19)

The circuit of claim 19, comprising an overflow control circuit (OVERFLOW CHECK) generating an overflow flag (OF) as logic combination among the most significant bits of said auxiliary string (MN-1; {overscore (MN-1)}) and of said first string (KN-1)

### Claim 25 (depends on 22)

The circuit of claim 22 for two's complementing said first string (K), wherein
each of said bits of the auxiliary string (MI) starting from the third least significant bit (M2) are obtained by ORing the immediately less significant bit (MI-1,) of said auxiliary string (M) and a corresponding bit of said string (KI-1);
said logic circuit means comprise an array of XOR gates, generating bits of said output string (Y) by XORing respective bits of said string to be complemented (K) and of said auxiliary string (M).

### Claim 26 (depends on 22)

The circuit of claim 22 for decrementing said first string (K), wherein
each of said bits of the auxiliary string (MI) starting from the third least significant bit (M2) are obtained by ORing the immediately less significant bit (MI-1) of said auxiliary string (M) and a corresponding bit of said string (KI-1);
said logic circuit means comprise an array of XOR gates, generating bits of a two's complement string (Z) by XORing respective bits of said string to be complemented (K) and of said auxiliary string (M), and an array of NOT gates each input with a bit of the two's complement string and generating a corresponding bit of said output string (Y).

### Claim 27 (depends on 22)

The circuit of claim 22 for incrementing said first string (K), wherein
each of said bits of the auxiliary string (MI) starting from the third least significant bit (M2) are obtained by ORing the immediately less significant bit (MI-1) of said auxiliary string (M) and the negated replica ({overscore (KI-1)}) of a corresponding bit of said string (KI-1);
said logic circuit means comprise an array of XOR gates, generating bits of said output string (Y) by XORing respective bits of said string to be complemented (K) and of said auxiliary string (M).

### Claim 28 (depends on 20, 24)

The circuit of claims 20 and 24 for two's complementing or decrementing said first string (K), wherein said overflow check circuit (OVERFLOW CHECK) is a logic AND gate generating said overflow flag (OF), input with the most significant bit of said first string (KN-1) and a negated replica of the most significant bit of said auxiliary string (MN-1)

### Claim 29 (depends on 23, 24)

The circuit of claims 23 and 24 for two's complementing or decrementing said first string (K), wherein said overflow check circuit (OVERFLOW CHECK) is a logic AND gate generating said overflow flag (OF), input with the most significant bits of said first string (KN-1) and of said auxiliary string ({overscore (MN-1)}).

### Claim 30 (depends on 20, 24)

The circuit of claims 20 and 24 for incrementing said first string (K), wherein said overflow check circuit (OVERFLOW CHECK) is a logic AND gate generating said overflow flag (OF), input with the negated replicas of the most significant bits of said first string (KN-1) and of said auxiliary string (MN-1).

### Claim 31 (depends on 23, 24)

The circuit of claims 23 and 24 for incrementing said first string (K), wherein said overflow check circuit (OVERFLOW CHECK) is a logic AND gate generating said overflow flag (OF), input with a negated replica of the most significant bit of said first string (KN-1) and the most significant bit of said auxiliary string ({overscore (MN-1)}).

### Claim 32 (depends on 22)

The circuit of claim 22 for incrementing or decrementing an input string (X) constituted by a number N of bits, comprising
an input terminal for receiving a command signal (ID) of the operation to be performed;
an array of N XOR gates each input with a respective bit of said input string (X) and with said command signal (ID) generating a corresponding bit of said first string (K);
each of said bits of the auxiliary string (MI) starting from the third least significant bit (M2) are generated by ORing the immediately less significant bit (MI-1) of said auxiliary string (M) and a corresponding bit of said string (KI-1);
said circuit logic means comprising an array of logic gates generating bits of said output string (Y) by XORing a negated replica of said selection command (ID) and the logic XOR of respective bits of said input string (X) and of said auxiliary string (M).

### Claim 33 (depends on 22)

The circuit of claim 22, comprising
a logic selection circuit (SEL) input with command signals (ID, TC) identifying the operation to be performed and generating a pair of selection signals first (INV_OUT) and second (INV_IN) whose logic state depends on the operation to be carried out,
an array of N input XOR gates each input with a respective bit of said input string (X) and said second selection signal (INV_IN), generating said first bit string (K),
each of said bits of the auxiliary string (MI) starting from the third least significant bit (M2) are obtained by ORing the immediately less significant bit (MI-1) of said auxiliary string (M) and a corresponding bit of said string (KI-1);
said logic circuit means comprising an array of logic gates generating bits of said output string (Y) by XORing said first selection signal (INV_OUT) and the logic XOR of respective bits of said input string (X) and of said auxiliary string (M).

### Claim 34 (depends on 28)

The circuit of claim 28 for two's complementing with correction of the output in case of overflow, wherein
each of said bits of the auxiliary string (MI) starting from the third least significant bit (M2) are obtained by ORing the immediately less significant bit (MI-1) of said auxiliary string (M) and a corresponding bit of said string (KI-1);
said logic circuit means comprise
an OR gate input with the most significant bit of said first string (KN-1) and the negated replica of the most significant bit of said auxiliary string (MN-1), generating the most significant bit of a two's complement string to be corrected (ZN-1),
an array of XOR gates generating the other bits of said two's complement string to be corrected (Z) by XORing corresponding bits of said first string (K) and of said auxiliary string (M); a correction circuit (CLIP) having p2 a NOT gate generating the most significant bit of said output string (YN-1) as negated replica of the most significant bit of said two's complement string to be corrected (ZN-1),
an array of N-1 OR gates generating respective other bits of said output string (Y), each gate being input with said overflow flag (OF) and with an output of a respective gate XOR of said array.

### Claim 35 (depends on 28)

The circuit of claim 28 for two's complementing or decrementing with correction of the output in case of overflow, having an input terminal receiving a selection signal (INV_OUT) of the operation to be performed, wherein
each of said bits of the auxiliary string (MI) starting from the third least significant bit (M2) are obtained by ORing the immediately less significant bit (MI-1) of said auxiliary string (M) and of a corresponding bit of said string (KI-1);
said logic circuit means comprise
an OR gate input with the most significant bit of said first string (KN-1) and the negated replica of the most significant bit of said auxiliary string (MN-1), generating the most significant bit of a two's complement string to be corrected (ZN-1),
an array of XOR gates generating the other bits of said two's complement string to be corrected (Z) by XORing corresponding bits of said first string (K) and of said auxiliary string (M);
an output logic circuit input with said two's complement string (Z), said overflow flag (OF) and said selection signal and said selection signal (INV_OUT), generating an output bit string (Y) equal to said two's complement string (Z) or obtained by negating all the bits thereof depending on the logic state of said selection signal (INV_OUT) and of said overflow flag (OF).

### Claim 36 (depends on 35)

The circuit of claim 35 for two's complementing or decrementing with correction of the output in case of overflow, wherein said output logic circuit comprises
a logic correction circuit (CLIP) generating a negated replica of said selection signal ({overscore (INV_OUT)}) and a correction signal (INVCLIP) by XORing said selection signal (INV_OUT) and said overflow flag (OF);
an array of N logic XOR gates, one of them being input with the most significant bit (ZN-1) of said two's complement bit string (Z) and with said negated replica ({overscore (INV_OUT)}) generating the most significant bit of the output string (YN-1), and each other XOR gate being input with a respective other bit of said two's complement string (Z) and said correction signal (INVCLIP) generating corresponding other bits of the output string (Y).

### Claim 37 (depends on 35)

A multifunction circuit (DIT) for decrementing, incrementing or two's complementing an input N bit string (X), comprising
a logic selection circuit (SEL) input with command signals (ID, TC) identifying the operation to be performed and generating a pair of selection signals first (INV_OUT) and second (INV_IN) whose logic state depends on the operation to be performed,
an array of N XOR input gates each input with a respective bit of said input string (X) and with said first logic signal (INV_IN), generating said first bit string (K),
a circuit for two's complementing or decrementing as defined in claim 35, input with said first bit string (K) and generating said output bit string (Y).

### Claim 38 (depends on 37)

The multifunction circuit (DIT) of claim 37, wherein said selection circuit (SEL) is input with a pair of command signals first (ID) and second (TC) and generates
said first logic signal (INV_OUT) by NORing said command signals (ID, TC);
said second logic signal (INV_IN) by ANDing said first command signal (ID) and a negated replica of said second command signal (TC).
