Browse Prior Art Database

Significant Bit Counter

IP.com Disclosure Number: IPCOM000083037D
Original Publication Date: 1975-Mar-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 3 page(s) / 64K

Publishing Venue

IBM

Related People

Ouchi, NK: AUTHOR

Abstract

The design of binary counters is well established in the art. However, the mechanisms necessary to utilize a portion of a fixed-length (fixed number of digits or bits) counter have not been explored. The significant-bit counter is an auxiliary counter that can be used to determine the number of significant digits or bits in a fixed-length counter, or to determine when all of the significant bits have gone to 0 irrespective of the states of the nonsignificant bits.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Significant Bit Counter

The design of binary counters is well established in the art. However, the mechanisms necessary to utilize a portion of a fixed-length (fixed number of digits or bits) counter have not been explored. The significant-bit counter is an auxiliary counter that can be used to determine the number of significant digits or bits in a fixed-length counter, or to determine when all of the significant bits have gone to 0 irrespective of the states of the nonsignificant bits.

In this discussion, the application of counters is limited to two cases: 1) The enumeration of items in a set the counting of items 2) The establishment of a set with a given number of items the counting out of items.

In case 1, the counter is initialized to 0 and incremented as each item is counted. The number of significant bits in the counter can be determined for an N-bit counter with bits labelled: b(0)b(1)b(2)...b(n-1) where b(0) is the highest order bit and b(n-1) is the lowest order bit. The following observations are made:
i) In the initial (zero) state, all the bits are zero, and the number of significant bits is one. (The "0"). ii) For any nonzero counter value, the most significant bit is always a logical "1", with all higher order bits at at a logical "0". iii) If bit b(i) is the most significant bit, then there are n-i significant bits in the counter and the number of significant bits increases by one when bit b(i-1) is set to a 1 and bit b(i) is reset to a 0.

Thus, the number of significant bits in the counter can be determined by the following algorithm: 1) Counter, C, is 0; significant-bit counter is set to 1. Let V(SB) denote the value in counter SB. 2) Monitor bit b(N-V(SB) When it changes from a 1 to a 0, increment SB. 3) Return to 2 until counting is complete. 4) When counting is complete V(SB) equals the number of significant bits in the counter.

The alternative methods of determining the 3/7 number of significant bits could be.: 1) Construct a tree network that examines the bits b(0),b(1) ...b(n-1) and generates the number of bits

(Image Omitted)

The complexity of such a network grows as the square of the number of bits in the main counter. 2) Construct the main counter from elements of a shift register. When the counting is complete, the number of leading 0's is counted by shifting. The number of significant bits is N(number of leading 0's). The logic is simple, but the counting of the significant bits requires a time overhead proportional to the number of bits in the counter.

In case 2, the counter is initialized to a count of the items to be counted out. These significant bits are placed in the counter with the least significant bit in b(n- 1), the lowest order bit position. The other bits are in ascending order. Bits in positions of order higher than the most significant bit can have any value and are ignored. The counting-out process is complete when the significant bits are all 0, irrespective of...