Collating bits from a byte source

• US 5,898,898 A
• Filed: 05/31/1996
• Issued: 04/27/1999
• Est. Priority Date: 05/31/1996
• Status: Expired due to Term

• Current Assignee: 8X8, Inc.
• Original Assignee: 8X8, Inc.
• Inventors: Kleck, James
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): VU, VIET DUY
• Application Number:
  US08/656,676
• Time in Patent Office: 1,061 Days
• Field of Search: 395/898, 395/411, 395/415, 395/416, 395/885, 341/67, 341/59, 341/60
• US Class Current: 712/300
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: H04L 12/6418 Hybrid transport

Abstract

A bit collation method is disclosed which requires a substantially fewer number of clock cycles than the prior art method in separating the bits in a source of bytes and collating them by bit position. A static look-up table is used to spread out the bits in a byte being collated. The look-up table enables simultaneous collation of all bits in a byte using only five clock cycles.

Claims

1. A method for collating a bit-group having a plurality of bits, comprising the steps of:

(a) retrieving a spread-out entry from a look-up table, said spread-out entry corresponding to said plurality of bits in said bit-group, said spread-out entry comprising bit-segments equal in number to said plurality of bits in said bit-group, each of said bit-segments having a first number of bit positions, and one bit position in each of said bit-segments being occupied by the corresponding bit in said bit-group, all other bit positions in each of said bit-segments being occupied by a predesignated bit value; and

(b) combining said spread-out entry with the contents of an accumulation register, placing the result in said accumulation register.

2. A method as recited in claim 1 wherein, said one bit position in each of said bit-segments in said spread-out entry is the least significant bit position in each of said bit-segments in said spread-out entry.

3. A method as recited in claim 2, wherein said accumulation register comprises bit-segments equal in number to said plurality of bits in said bit-group, each of said bit-segments in said accumulation register having a second number of bit positions.

4. A method as recited in claim 3, further comprising the step of:

(c) clearing the most significant bit position in each of said bit-segments in said accumulation register immediately after step (a).

5. A method as recited in claim 4, further comprising the step of:

(d) shifting the contents of said accumulation register by one bit position to the left, immediately after step (c).

6. A method as recited in claim 5 wherein, said predesignated bit value is a 0.

7. A method as recited in claim 6 wherein, "combining" in said combining step refers to a logical OR operation.

8. A method as recited in claim 7, further comprising the step of:

(e) comparing the contents of each of said bit-segments in said accumulation register with a predesignated bit-pattern, after step (b).

9. A method as recited in claim 8 wherein, each of said first and second number of bit positions are equal in number to the number of bits in said predesignated bit-pattern.

10. A method as recited in claim 8 wherein, each of said first and second number of bit positions are greater in number than the number of bits in said predesignated bit-pattern.

11. A method as recited in claim 6 wherein, "combining" in said combining step refers to a logical ADD operation.

12. A method for collating bits from a source of bit-groups, each bit-group having a first plurality of bits, comprising the steps of:

(a) retrieving a first bit-group from said source of bit-groups;

(b) retrieving a spread-out entry from a look-up table, said spread-out entry corresponding to said first bit-group, said look-up table having one spread-out entry for every possible bit combination in a bit-group, each bit combination being used as an index for accessing the corresponding spread-out entry in the look-up table, each spread-out entry comprising bit-segments equal in number to said first plurality of bits, each of said bit-segments having a first number of bit positions, and the least significant bit position in each of said bit-segments being occupied by the corresponding bit in the bit-group being collated, all other bit positions in each of said bit-segments being occupied by a predesignated bit value;

(c) shifting the contents of an accumulation register one bit position to the left; and

(d) combining the contents of said spread-out entry with the contents of said accumulation register, placing the result in said accumulation register.

13. A method as recited in claim 12, wherein said accumulation register comprises bit-segments equal in number to said first plurality of bits, each of said bit-segments in said accumulation register having a second number of bit positions.

14. A method as recited in claim 13, further comprising the step of:

(e) clearing the most significant bit position in each of said bit-segments in said accumulation register immediately after step (b).

15. A method as recited in claim 14 wherein, said predesignated bit value is a 0.

16. A method as recited in claim 15 wherein, "combining" in said combining step refers to a logical OR operation.

17. A method as recited in claim 16, further comprising the steps of:

(f) repeating steps (a) through (e) on "X" number of successive bit-groups from said source of bit-groups wherein, "X" is an integer which equals the number of bits in a predesignated bit-pattern; and

(g) comparing the contents of each of said bit-segments in said accumulation register with said predesignated bit-pattern, to determine whether the contents of any of said bit-segments in said accumulation register match said predesignated bit-pattern.

18. A method as recited in claim 17 wherein, each of said first and second number of bit positions are equal in number to the number of bits in said predesignated bit-pattern.

19. A method as recited in claim 17 wherein, each of said first and second number of bit positions are greater in number than the number of bits in said predesignated bit-pattern.

20. A method as recited in claim 12 wherein, said source of bit-groups is a stream of bytes received through a communication medium.

21. A method as recited in claim 15 wherein, "combining" in said combining step refers to a logical ADD operation.

22. A method for collating a bit-group having a plurality of bits, comprising the steps of:

(a) retrieving a spread-out entry from a look-up table, said spread-out entry corresponding to said plurality of bits in said bit-group, said spread-out entry comprising bit-segments equal in number to said plurality of bits in said bit-group, each of said bit-segments having a first number of bit positions, and one bit position in each of said bit-segments being occupied by the inverted bit value of the corresponding bit in said bit-group, all other bit positions in each of said bit-segments being occupied by a predesignated bit value; and

(b) combining said spread-out entry with the contents of an accumulation register, placing the result in said accumulation register.

23. A method as recited in claim 22 wherein, said one bit position in each of said bit-segments in said spread-out entry is the least significant bit position in each of said bit-segments in said spread-out entry.

24. A method as recited in claim 23, wherein said accumulation register comprises bit-segments equal in number to said plurality of bits in said bit-group, each of said bit-segments in said accumulation register having a second number of bit positions.

25. A method as recited in claim 24, further comprising the step of :

(c) clearing the most significant bit position in each of said bit-segments in said accumulation register immediately after step (a).

26. A method as recited in claim 25, further comprising the step of:

(d) shifting the contents of said accumulation register by one bit position to the left, immediately after step (c).

27. A method as recited in claim 26 wherein, said predesignated bit value is a 1.

28. A method as recited in claim 27 wherein, "combining" in said combining step refers to a logical AND operation.

29. A computer readable medium storing a computer program, the program comprising:

means for collating a bit-group having a plurality of bits, further comprising;

means for retrieving a spread-out entry from a look-up table, said spread-out entry corresponding to said plurality of bits in said bit-group, said spread-out entry comprising bit-segments equal in number to said plurality of bits in said bit-group, each of said bit-segments having a first number of bit positions, and one bit position in each of said bit-segments being occupied by the corresponding bit in said bit-group, all other bit positions in each of said bit-segments being occupied by a predesignated bit value; and

means for combining said spread-out entry with the contents of an accumulation register and placing the result in said accumulation register.

30. A computer readable medium as recited in claim 29 wherein said one bit position in each of said bit-segments in said spread-out entry is the least significant bit position in each of said bit-segments in said spread-out entry.

31. A computer readable medium as recited in claim 30 wherein said accumulation register comprises bit-segments equal in number to said plurality of bits in said bit-group, each of said bit-segments in said accumulation register having a second number of bit positions.

32. A computer readable medium as recited in claim 31, further comprising:

means for clearing the most significant bit position in each of said bit-segments in said accumulation register immediately after said spread-out entry is retrieved from said look-up table.

33. A computer readable medium as recited in claim 32, further comprising:

means for shifting the contents of said accumulation register by one bit position to the left immediately after the most significant bit position in each of said bit-segments in said accumulation register is cleared.

34. A computer readable medium as recited in claim 33 wherein, said predesignated bit value is a 0.

35. A computer readable medium as recited in claim 34 wherein, said combining means performs an OR operation.

36. A computer readable medium as recited in claim 35, further comprising:

means for comparing the contents of each of said bit-segments in said accumulation register with a predesignated bit-pattern after said spread-out entry and the contents of an accumulation register are combined and placed in said accumulation register.

37. A computer readable medium as recited in claim 36 wherein each of said first and second number of bit positions are equal in number to the number of bits in said predesignated bit-pattern.

38. A computer readable medium as recited in claim 36 wherein each of said first and second number of bit positions are greater in number than the number of bits in said predesignated bit-pattern.

39. A computer readable medium as recited in claim 34 wherein, said combining means performs an ADD operation.