Home > Articles > Software Development & Management > Architecture and Design

  • Print
  • + Share This
This chapter is from the book

11.2 Binary Integers and Overflow

We have identified a concern about register overflow in a CIC filter. To help understand the overflow we now review a number of ways binary numbers are used to represent integers. Equation (11.11) presents the standard notation for binary numbers.

Equation 11.11

11equ11.gif


Standard notation assigns the least significant bit to the right so that (11.11) can be written specifically as in (11.12).

Equation 11.12

11equ12.gif


Alternatively, we can represent the binary number by an ordered set, with position in the ordered set implying the appropriate power of 2. This is the standard notation we use in decimal notation. This notation form is shown in (11.13).

Equation 11.13

11equ13.gif


An example of the binary representation of a set of decimal integers with implied powers of 2 is shown in Table 11-1.

Table 11-1. Decimal Integers and Their 3-bit Binary Representation

Decimal

Binary

0

000

1

001

2

010

3

011

4

100

5

101

6

110

7

111

The integers identified in Table 11-1 are all positive. If we require both positive and negative representations of our integers we have to add a sign modifier. The form of a binary number with a sign modifier is shown in (11.14)

Equation 11.14

11equ14.gif


In sign-magnitude notation, the sign bit is a multiplier +1 or –1. In offset-binary notation, the sign bit is an added term ab2b and the number is decoded by subtracting 2b from its binary representation. In 2's-complement notation, the sign bit is an added –ab2b. Examples of 4-bit binary numbers in the three binary representations are shown in Table 11-2.

Table 11-2. Decimal Integers and Their Signed 4-Bit Binary Representation

Decimal

Sign-magnitude

Offset-binary

2's-complement

+7

0111

1111

0111

+6

0110

1110

0110

+5

0101

1101

0101

+4

0100

1 100

0100

+3

0011

1011

0011

+2

0010

1010

0010

+1

0001

1001

0001

+0

0000

1000

0000

-0

1000

N/A

N/A

-1

1001

0111

1111

-2

1010

0110

1110

-3

1011

0101

1101

-4

1100

0100

1100

-5

1101

0011

1011

-6

1110

0010

1010

-7

1111

0001

1001

-8

N/A

0000

1000

Figure 11.7 presents the overflow behavior of a 2's-complement binary counter. The overflow is, as expected, periodic. The unique behavior of the overflow is that the difference between points in the counter (or on circle) is correct even if the counter has experienced an overflow. It is well known that intermediate overflows of a 2's-complement accumulator lead to the correct answer as long as the accumulator is wide enough to hold the correct answer.

11fig08.gifFigure 11.7 Overflow Behavior of 2's-Complement Binary Counter

As an example, let us examine the step response of a CIC with 4-units of delay in the comb filter. Here the number 1 is added to the accumulator on each clock cycle, and the comb filter following the accumulator forms the difference between the current input and the input formed 4-units ago. The sequence of outputs values is presented in Table 11-3, where we see that the output of the comb filter is correct in spite of the overflowing accumulator.

Table 11-3. Comb Filter Operating on Output of Overflowing Accumulator

w(n)

math

w(n-4)

 

y(n)

0

0

=

0

1

0

=

1

2

0

=

2

3

0

=

3

4

0

=

4

5

1

=

4

6

2

=

4

7

3

=

4

–8

4

=

–12 = 4

–7

5

=

–12 = 4

–6

6

=

–12 = 4

–5

–7

=

–12 = 4

–4

–8

=

4

–3

–7

=

4

–2

–6

=

4

–1

–5

=

4

If the accumulator is sufficiently wide, and if the CIC filter is performed with 2's-complement arithmetic, the CIC output will be correct in spite of the internal overflow of the integrator. By sufficiently wide we mean that the accumulator width must be the sum of the number of input bits and the number of bits required to accommodate the growth M of the M-tap prototype filter upon which the CIC is based. For instance, with 10-bit input data and a 100-tap boxcar filter with a gain of 100, we require 7-bits of growth for a bit field width of 17-bits. The accumulator must have 17 or more bits to implement the 100-tap boxcar filter as a CIC filter. Bit width is addressed in more detail in a later section.

  • + Share This
  • 🔖 Save To Your Account