Upon receiving an encoded message with errors, evaluating it at the roots of the generator polynomial will result in the elimination of the initial terms, leaving behind a set of “syndromes.” These syndromes are dependent on the error locations and values. To convert syndromes into error locations and values, the wiki article presents four methods, with Berlekamp-Massey and Euclid as the primary methods utilized.
The 2’s Complement Number System is commonly utilized in computer architecture, and the focus of this discussion will primarily be on overflow in relation to this system.
The 2’s Complement number system with N bits has a range of values from
. In this system, a 4-bit number can represent values ranging from -8 to 7, while a 5-bit number can represent values ranging from -16 to 15.
When you add two N-bit 2’s complement numbers, an overflow happens if the result is too big to fit into the N-bit group.
N-Bit Fixed registers are used in computers. When N-Bit Numbers are added, the result is a maximum N+1 Bit number. The additional Bit is saved in the carry Flag. However, the carry Flag does not necessarily indicate overflow.
The sum of 7 and 1 in a 4-bit system should equal 8, but since 8 is beyond the range of a 4-bit 2’s complement number, it cannot be represented. Instead, adding two positive numbers resulted in a negative answer (-8) with a carry of 0. Detecting overflow and handling this scenario is typically the responsibility of the programmer.
The concept of detecting overflow is related to instances where there is an excess of something.
- When two negative numbers are added, the resulting answer is positive.
- The sum of two numbers with positive values results in a negative output.
To detect overflow during N-bit addition of 2’s complement numbers, one can check the Most Significant Bit (MSB) of two operands and the answer. However, rather than using a 3-bit comparator, overflow can also be detected with a 2-bit comparator by examining the Carry-in (C-in) and Carry-out (C-out) from the MSBs.
An overflow situation arises when C-in exceeds C-out. This condition, which is illustrated in
, can be understood by the following analysis.
The first Figure shows two numbers with MSBs of 0, indicating that they are positive. If C-in is set to 1, the MSB of the answer will become 1, indicating a negative answer (Overflow), and the C-out will be 0, resulting in an overflow.
The second Figure displays two negative numbers with a MSB of 1. When C-in is set to 0, the answer’s MSB becomes 0 indicating a positive result (Overflow), while C-out becomes 1, indicating overflow. By experimenting with different combinations of c-in, c-out, and MSB’s, readers can verify overflow.
Detecting Overflow can be accomplished simply through Carry-in and Carry-out operations at MSBs.
The XOR Gate mentioned can serve as an overflow detector.