Bit string compressor with boolean operation processing capability

• US 5,036,457 A
• Filed: 04/22/1988
• Issued: 07/30/1991
• Est. Priority Date: 09/24/1987
• Status: Expired due to Term

• Current Assignee: SAND Technology, Inc.
• Original Assignee: Nucleus International Corporation
• Inventors: Caldwell, Douglas W., Glaser, Edward L., Glaser, Eliot D., DesJardins, Paul R.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Kriess, Kevin A.
• Application Number:
  US07/185,888
• Time in Patent Office: 1,194 Days
• Field of Search: 364/200, 364/900, 364/300, 341/50, 341/51, 341/55, 341/95
• US Class Current: 703/22
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

Abstract

An apparatus and method, for use with a computer, for converting an uncompressed one-dimensional array of binary bits into a compressed binary bit string and/or for processing a Boolean operation on a first and a second compressed bit string. The first and second bit strings each contain one or more impulses. An impulse contains a run, which is a string of one or more bits of the same binary value, and an ending bit having a polarity opposite the polarity of the run. The impulses are encoded in one or more compressed impulse formats. Each compressed impulse format contains at least a first and a second indicator. The first indicator is for indicating the binary value of one or more same polarity bits of the run and the second indicator is for indicating the length of bits of the impulse. The length of bits is a quantity of the same polarity bits of the run and/or the ending bit having a polarity opposite the run.

Claims

1. A method using a computer for converting a string of binary bits of indefinite length into compressed impulse format, said method comprising the steps of:

grouping the successive bits of said string into a corresponding sequence of one or more uncompressed impulses which together constitute substantially the entire bit string, each said one or more impulses comprising a run of one or more contiguous bits of said string having the same polarity followed by the next bit of said string having a polarity opposite from said same polarity of the associated impulse; and

encoding each said one or more uncompressed impulses in sequence into a corresponding sequence of compressed impulse formats, one compressed format for each and every uncompressed impulse, said compressed impulse format comprising first and second binary bit coded indicators, said first indicator indicating the polarity of said one or more same polarity bits of the corresponding uncompressed impulse and said second indicator indicating the quantity of said same polarity bits grouped in the corresponding uncompressed impulse.

2. The method of claim 1 wherein the step of encoding comprises forming in said second indicator one or more binary words for representing extended length impulses.

3. The method of claim 1 wherein the step of encoding comprises forming said second indicator to indicate the quantity of the said same polarity bits with said next bit of opposite polarity.

4. The method of claim 1 wherein the step of encoding comprises the step of encoding one or more of said uncompressed impulses into a common compressed impulse format and comprising the step of forming in such common compressed impulse format an individual one of said first indicator for each of said one or more uncompressed impulses to be represented in such common compressed impulse format.

5. The method of claim 4 wherein the step of encoding comprises the step of forming in such common compressed impulse format an individual one of said second indicators for each of said one or more uncompressed impulses to be represented in such common compressed impulse format.

6. The method of claim 5 comprising the step of forming an indication in the common compressed impulse format of the number of said one or more impulses represented therein.

7. The method of claim 1 further comprising:

the step of determining the quantity of bits in the uncompressed impulses for one or more of said impulses; and

the step of encoding including the steps of forming common format words having said compressed impulse format, and forming, in each of said common format words, a representation of said first and said second indicators for each of a variable number of said one or more uncompressed impulses, where such variable number varies depending on the quantity of bits determined.

8. The method of claim 7 wherein said common format words are of the same length for a plurality of different numbers of said uncompressed impulses represented therein.

9. The method of claim 7 comprising the step of forming in each said common word a format indicator which is an indication of the number of said one or more uncompressed impulses.

10. The method of claim 7 comprising the step of forming said common format words of the same length for different numbers of said one or more uncompressed impulses represented in the same common format word.

11. The method of claim 9 comprising the steps of setting an initial value in the format indicator for a first number of uncompressed impulses with a first impulse, and selectively modifying the initial format indicator at least one dependent on the quantity of bits determined for at least one further uncompressed impulse.

12. The method of claim 9 comprising the step of setting the format indicator in the common format word for a first number of uncompressed impulses in the common format word and then modifying the format indicator to represent a different number of impulses depending on the number of impulses represented in the common format word.

13. The method of claim 1 wherein the step of encoding comprises the step of encoding one or more of said uncompressed impulses into a common compressed impulse format and comprising the step of forming a polarity bit for each said one or more uncompressed impulses, each said polarity bit having a binary value corresponding to said one or more same polarity bits for each said one or more uncompressed impulses.

14. The method of claim 1 wherein said step for encoding said one or more impulses into said compressed impulse format further comprises the step of:

encoding said one or more uncompressed impulses into a first compressed impulse format when encoding an impulse having a length of bits of 2 to 31 bits, a second compressed impulse format when encoding an impulse having a length of bits of 32 to 2³² -1 bits, a third compressed impulse format when encoding two impulses, each having a length of bits of 2 to 5 bits, or a fourth compressed impulse format when encoding three impulses, each having a length of bits of 2 or 3 bits.

15. The method of claim 14 wherein the step for encoding said first compressed impulse format further comprises the steps of:

forming a pair of bits for indicating said first format;

forming in said first indicator of said first format a polarity bit for indicating a binary value of said impulse; and

forming in said second indicator of said first format five bits for indicating said length of bits of said impulse.

16. The method of claim 14 wherein the step for encoding said second format further comprises the steps of:

forming a pair of bits for indicating said second format;

forming in said first indicator of said second format a polarity bit for indicating a binary value of said impulse;

forming in said second indicator of said second format, one, two, three or four eight-bit words for indicating the length of said impulse; and

forming in said second indicator two bits for indicating whether one, two, three or four of said words are necessary for encoding said impulse.

17. The method of claim 14 wherein the step for encoding said third format further comprises the steps of:

forming a pair of bits for indicating said third format;

forming in said first indicator of said third format two polarity bits, said polarity bits indicating a binary value for each said impulse; and

forming in said second indicator of said third format a first and a second pair of bits indicating a corresponding length for each said uncompressed impulse.

18. The method of claim 17 further comprising the step of converting said third format into said first format, said first format for encoding an impulse, and said impulse having a length 2 to 5 bits, said step for converting said third format comprising the steps:

converting said pair of bits for indicating said third format, to indicate said first format;

whereby converting said third format into said first format.

19. The method of claim 18 further comprising the steps of:

placing a pair of zero'"'"'s into said second pair of bits of said second indicator of said third format; and

placing a zero in said second polarity bit of said first indicator of said third format.

20. The method of claim 14 wherein the step for encoding said fourth format further comprises the steps of:

forming in said fourth format a pair of bits for indicating said fourth format;

forming in said first indicator of said fourth format three polarity bits said for indicating a polarity for each said impulse; and

forming in said second indicator of said fourth format a first, a second, and a third bit, said first, said second and said third bits for indicating a corresponding length for each said impulse.

21. The method of claim 20 further comprising the step for converting said fourth format into said third format, said third format for encoding a first and a second impulse, and said first and said second impulses having a length of 2 or 3 bits, said step for converting said fourth format comprising the steps:

converting said pair of bits, for indicating said fourth format, to indicate said third format;

whereby converting said fourth format into said third format.

22. The method of claim 21 further comprising the steps of:

placing a zero in said third bit of said second indicator of said fourth format; and

placing a zero in said third polarity bit of said first indicator of said fourth format.

23. The method of claim 20 further comprising the step of converting said fourth format into said first format, said first format for encoding an impulse, and said impulse having a length of 2 or 3 bits, said step for converting said fourth format comprising the steps:

converting said pair of bits for indicating said format, to indicate said first format;

whereby converting said fourth format into said first format.

24. The method of claim 23 further comprising the steps of:

placing a zero into said third and said second polarity bits of said first indicator of said fourth format; and

placing a zero into said third and said second bits of said second indicator of said fourth format.

25. An apparatus for using a computer for converting a string of consecutive binary bits into a compressed impulse format comprising:

means for separating said bit string into one or more uncompressed impulses, which together constitute substantially the entire bit string, each said one or more uncompressed impulses comprising a run of one or more contiguous bits of the same polarity in said bit string followed by a next bit having a polarity opposite from said same polarity of the associated impulse; and

means for encoding each and everyone of said one or more uncompressed impulses into a corresponding sequence of compressed impulse formats, there being one compressed impulse format for each uncompressed impulse, each said compressed impulse format comprising first and second binary coded indicators, said first indicator indicating the polarity of said one or more same polarity bits of the corresponding uncompressed impulse and said second indicator indicating the quantity of said same polarity bits of the corresponding uncompressed impulse.

26. The apparatus of claim 25 wherein the means for encoding comprises forming in said second indicator one or more binary words for representing extended length impulses.

27. The apparatus of claim 25 wherein the means for encoding comprises means for forming said second indicator to indicate the quantity of said same polarity bits with said next bit of opposite polarity.

28. The apparatus of claim 25 wherein the means for encoding comprises means for encoding one or more of said uncompressed impulses into a common compressed impulse format and comprising means for forming in such common compressed impulse format an individual one of said first indicator for each of said one or more uncompressed impulses to be represented in such common compressed impulse format.

29. The apparatus of claim 28 wherein the means for encoding into a common compressed impulse format comprises means for forming in such common compressed impulse format an individual one of said second indicators for each of said one or more uncompressed impulses to be represented in such common compressed impulse format.

30. The apparatus of claim 29 further comprising means for forming an indication in the common compressed impulse format of the number of said one or more impulses represented therein.

31. The apparatus of claim 25 further comprising:

means for determining the quantity of bits in the impulses for one or more of said impulses;

the means for encoding, including the means for forming common format words, having said compressed impulse format, and means for forming, in each of said common format words, a representation of said first and said second indicators for each of a variable number of said one or more impulses, where such variable number varies depending on the quantity of bits determined.

32. The apparatus of claim 31 wherein said common format words are of the same length for a plurality of different numbers of said uncompressed impulses represented therein.

33. The apparatus of claim 31 further comprising means for forming in each said common word a format indicator which is an indication of the number of said uncompressed impulses.

34. The apparatus of claim 31 comprising means for forming said common format words of the same length for different numbers of said uncompressed impulses represented in the same common format word.

35. The apparatus of claim 33 comprising means for setting an initial value in the format indicator for a first number of uncompressed impulses with a first impulse, and means for selectively modifying the initial format indicator at least one dependent on the quantity of bits determined for at least one further uncompressed impulse.

36. The apparatus of claim 33 comprising means for setting the format indicator in the common format word for a first number of uncompressed impulses in the common format word and means for modifying the format indicator to represent a different number of impulses depending on the number of impulses represented in the common format word.

37. The apparatus of claim 25 wherein the means for encoding comprises means for encoding one or more of said uncompressed impulses into a common compressed impulse format and comprising means for forming a bit for each said one or more uncompressed impulses, said polarity bit having a polarity corresponding to said one or more same polarity bits for each said one or more uncompressed impulses.

38. The apparatus of claim 25 wherein said means for encoding said one or more impulses into said compressed impulse format further comprises means for encoding said uncompressed impulse into a first compressed impulse format when encoding an impulse having a length of bits of 2 to 31 bits, a second compressed impulse format when encoding an impulse having a length of bits of 2 to 2³² -1 bits, a third compressed impulse format when encoding two impulses each having a length of bits of 2 to 5 bits, or a fourth compressed impulse format for encoding three impulses, each having a length of bits of 2 or 3 bits.

39. The apparatus of claim 38 wherein the means for encoding said first compressed impulse format further comprises:

means for forming a pair of bits for indicating said first format;

means for forming in said first indicator of said first format a polarity bit for indicating a binary value of said impulse; and

means for forming in said second indicator of said first format five bits for indicating the length of bits of said impulse.

41. The apparatus of claim 38 wherein the means for encoding said third format further comprises:

means for forming a pair of bits for indicting said third format;

means for forming in said first indicator of said third format two polarity bits indicating a binary value for each said impulse;

means for forming in said second indication of said third format a first and a second pair of bits indicating a corresponding length for each said second uncompressed impulse.

42. The apparatus of claim 41 further comprising means for converting said third format into said first format, said first format for encoding an impulse, and said impulse having a length of 2 to 5 bits, said means for converting said fourth format comprises:

means for converting said pair of bits for indicating said third format, to indicate said first format;

whereby providing means for converting said third format into said first format.

43. The apparatus of claim 42 further comprises:

means for placing a pair of zero'"'"'s into said second pair of bits of said second indicator of said third format; and

means for placing a zero in said second polarity bit of said first indicator of said third format.

44. The apparatus of claim 38 wherein the means for encoding said fourth format further comprises:

means for forming in said fourth format a pair of bits for indicating said fourth format;

means for forming in said first indicator of said fourth format three polarity bits for indicating a polarity for each said impulse; and

means for forming in said second indicator of said fourth format a first, a second, and a third bit, said first, said second and said third bits for indicating a corresponding length for each said impulse.

45. The apparatus of claim 44 further comprising means for converting said fourth format into said third format, said third format for encoding a first and a second impulse, and said first and said second impulses having a length of 2 or 3 bits, said means for converting said fourth format comprises:

means for converting said pair of bits, for indicating said fourth format, to indicate said third format;

whereby providing means for converting said fourth format into said third format.

46. The apparatus of claim 45 further comprises:

means for placing a zero in said third bit of said second indicator of said fourth format; and

means for placing a zero in said third polarity bit of said first indicator of said fourth format.

47. The apparatus of claim 44 further comprising the means for converting said fourth format into said first format, said first format for encoding an impulse, and said impulse having a length of 2 or 3 bits, said means for converting said fourth format comprises:

means for converting said pair of bits for indicating said format, to indicate said first format; and

whereby providing means for converting said fourth format into said first format.

48. The apparatus of claim 47 further comprises:

means for placing a zero into said third and said second polarity bits of said first indicator of said fourth format; and

means for placing a zero into said third and said second bits of said second indicator of said fourth format.

40. The apparatus of claim 40 wherein the means for encoding said second format further comprises:

means for forming a pair of bits for indicating said second format;

means for forming in said first indicator of said second format a polarity bit for indicating said binary value of said impulse; and

means for forming in said second indicator of said second format, one, two, three or four eight-bit words for indicating the length of said impulse; and

means for forming in said second indicator two bits for indicating whether one, two, three or four of said words are necessary for ending said impulse.

49. A method using a computer for efficiently performing Boolean-type operations on a pair of binary bit strings in which each binary bit string is represented by a series of compressed impulse formats, each compressed impulse format comprising a binary polarity representation and a corresponding length representation, the polarity representation representing the binary value of one or more contiguous binary bits of the same binary value followed by a binary bit of the opposite binary value in a corresponding bit string and the length representation representing the quantity of such contiguous binary bits of the same value, the method comprising the steps of:

processing, according to a selected operation, a first series of compressed impulse formats representing a first one of the bit strings with a second series of the compressed impulse formats representing a second one of the bit strings, and forming in response to said selected operation an intermediate format result that represents a resultant bit string, the intermediate format result comprising a series of compressed impulse formats with intermixed run representations where each such run representation represents a series of binary bits of the same binary value in the resultant bit string.

50. The method of claim 49 further comprising the step of combining the series of compressed impulse formats and the run representations in the intermediate format result into a series of contiguous compressed impulse formats representing said resultant bit string.

51. The method of claim 50 wherein the step of processing comprises the step of forming the intermediate format result with said series of compressed impulse formats and run representations, with at least one of the run representations adjacent to at least one of the compressed impulse formats in the series.

52. The method of claim 50 wherein the step of combining comprises the step of combining at least one of said run representations with one of said compressed impulse formats to form, in place thereof, a further compressed impulse format.

53. The method of claim 55 wherein the step of forming a further compressed impulse format comprises the steps of:

if the at least one run representation and the compressed impulse format which are being combined are for bits of the same binary value, forming in such further compressed impulse format a polarity representation for such same binary value bits and a length representation for the total quantity of the bits of the same binary value in said at least one run and the compressed impulse format which are being combined.

54. The method of claim 50 wherein the step of combining comprises the step of combining at least one of said run representations with a compressed impulse format to form, in place thereof, a first and a second compressed impulse format.

55. The method of claim 54 wherein the step of forming said first and said second compressed impulse formats comprises the steps of:

if the at least one run representation and the compressed impulse format, which are being combined, are for bits of different binary values, forming in such first compressed impulse format a polarity representation for said binary value of said run and a length representation for the total quantity of the bits of the same binary value and for forming in such second compressed impulse format a polarity representation corresponding to said polarity of said compressed impulse format and a length representation for the total quantity of the bits of the compressed impulse format less one bit.

56. An apparatus using a computer for efficiently performing Boolean-type operation on a pair of binary bit strings in which each binary bit string is represented by a series of compressed impulse formats, each compressed impulse format comprising a polarity representation and a corresponding length representation, the polarity representation representing the binary value of one or more contiguous binary bits of the same binary value and a binary bit of the opposite binary value in a corresponding bit string and the length representation, in the same pair, representing the quantity of such contiguous binary bits of the same value, the method comprising:

means for processing, according to a selected operation, a first series of the compressed impulse formats representing a first one of the bit strings with a second one of the bit strings, and means responsive to said processing means for forming an intermediate format result that represents a resultant bit string according to said selected operation, the intermediate format result comprising a series of the compressed impulse formats and intermixed plural run representations where each such run representation represents a series of binary bits of the same binary value in the resultant bit string.

57. The apparatus of claim 56 further comprising means for combining the series of compressed impulse formats and run representations in the intermediate format result into a series of contiguous compressed impulse formats representing said resultant bit string.

58. The apparatus of claim 56 or 57 wherein the means for processing further comprises means for forming the intermediate format result with said series of compressed impulse formats and run representations, with at least one of the run representations adjacent to at least one of the compressed impulse formats in the series.

59. The apparatus of claim 57 wherein the means for combining comprises the means of combining at least one of said run representations with one of said compressed impulse formats to form, in place thereof, a further compressed impulse format.

60. The apparatus of claim 59 wherein the means for forming a further compressed impulse format comprises:

means responsive to the combining of run representations with a compressed impulse format having bits of the same binary value for forming in such further compressed impulse format a polarity representation for such same binary value bits and a length representation for the total quantity of the bits of the same binary value in said at least one run and the compressed impulse format which are being combined.

61. The apparatus of claim 57 wherein the means for combining further comprises means for combining at least one of said run representations with a compressed impulse format to form, in place thereof, a first and a second compressed impulse formats.

62. The apparatus of claim 56 wherein the means for forming said first and said second compressed impulse formats comprises:

means responsive to run representations and a compressed impulse format, which are being combined, that are for bits of different binary values for forming in such first compressed impulse format a polarity representation for said binary value of said run and a length representation for the total quality of the bits of the same binary value and means for forming in such second compressed impulse format a polarity representation corresponding to said polarity of said compressed impulse format and a length representation for the total quantity of the bits of the compressed impulse format less one bit.

63. A method using a computer for creating and processing a compressed representation of a set of data, said method comprising the steps of:

separating a bit string into one or more impulses, each said one or more impulses comprising a run of one or more contiguous bits of the same polarity and an ending bit at one end of the contiguous bits having a polarity opposite from said same polarity of the associated impulse;

encoding said one or more impulses into a corresponding compressed impulse format, each said compressed impulse format comprising a first and a second indicator, said first indicator indicating a polarity of said one or more same polarity bits of the corresponding impulse and said second indicator indicating the quantity of said same polarity bits; and

processing, according to a selected operation, a first series of the compressed impulse formats representing a first one of the bit strings with a second series of compressed impulse formats representing a second one of the bit strings, and thereby forming a resultant bit string, comprising a series of compressed impulse formats, if any, and intermixed, runs representations, if any, where each such run representation represents a series of binary bits of the same binary value in the resultant bit string.

64. The method of claim 63 further comprising the step of converting the resultant series of compressed impulse formats and run representations into a series of contiguous compressed impulse formats representing the resultant bit string.

65. The method of claim 63 or 64 comprising the step of storing each said compressed impulse format into a memory.

66. The method of claim 63 or 64 wherein the step for encoding comprises forming said second indicator to indicate the quantity of the said same polarity bits with said ending bit having said opposite polarity.

67. An apparatus using a computer for creating and processing a compressed representation of a set of data, said apparatus comprising:

means for separating a bit string into one or more impulses, each said one or more impulses comprising a run of one or more bits of the same polarity and an ending bit at one end of the contiguous bits having a polarity opposite from said same polarity of the associated impulse;

means for encoding said one or more impulses into a corresponding compressed impulse format, each said compressed impulse format comprising a first and a second indicator, said first indicator indicating a polarity of said one or more same polarity bits of the corresponding impulse and said second indicator indicating the quantity the said same polarity bits; and

means for processing, according to a selected operation, a first series of the compressed impulse formats representing a first one of the bit strings with a second series of the compressed impulse formats representing a second one of the bit strings, and thereby forming a resultant bit string comprising a series of the compressed impulse formats, if any, and intermixed, runs representations, if any, where each such run representation represents a series of binary bits of the same binary value in the resultant bit string.

68. The apparatus of claim 67 further comprising means for converting the resultant series of compressed impulse formats and run representations into a series of contiguous compressed impulse formats representing the resultant bit string.

69. The apparatus of claim 67 or 68 comprising the means for storing each said compressed impulse formats into a memory.

70. The apparatus of claim 67 or 68 wherein the means for encoding comprises means for forming in said second indicator an indication of the quantity of the said same polarity bits and said associated ending bit having said appropriate polarity.

71. A method using a computer for efficiently processing an operation on a first and a second impulse to determine a resultant run or impulse, said first and said second impulses comprising a run, said run comprising a string of one or more contiguous bits of a same polarity, and each said impulse comprising an ending bit at one end of the contiguous bits having an opposite polarity, said method for processing said impulses comprising the steps of:

comparing said length of said first impulse with said length of said second impulse to determine a minimum length, said minimum length being the length of said resultant run or impulse;

determining said polarity of said same polarity bits for said first and said second impulses; and

processing a selected operation on said first and said second impulses to determine whether said resultant bit string is a run or an impulse.

72. The method claim 71 further comprising the step of comparing said length of said first impulse with said length of said second impulse to determine whether the length of said first impulse is less than, greater than, or equal to the length of said second impulse.

73. The method claim 71 further comprising the step of storing said polarity, said type (run or impulse) and said length of one or more of said runs or impulses into a temporary memory and combining a plurality of said runs into a single said run.

74. The method of claim 71 or 72 further comprising the step of storing said polarity (run or impulse) and said length of one or more of said runs or impulses into a temporary memory area and combining said one or more runs or impulses into one or more impulses.

75. The method of claim 71 wherein said step for processing said selected operation further includes the step of forming an index table to determine said selected operation, said index table comprising a plurality of said operations.

76. The method of claim 75 wherein said step of forming an index table further comprises the step of representing each said operation by one or more subtables, each said subtable comprising a first, a second, and a third index, said first index for identifying a polarity of said first impulse, said second index for identifying a polarity of said second impulse, and said third index for identifying whether the length of said first impulse is less than, greater than, or equal to the length of said second impulse.

77. The method of claim 76 wherein said step for forming said index table further comprises the step of referencing said first, said second, and said third indexes to reference said selected operations.

78. The method of claim 71 wherein said step for performing a selected operations further comprises the step of determining whether said first and said second impulses are equal or unequal in length.

79. The method of claim 71 wherein said step for processing said selected operation further includes the step of performing a Boolean operation.

80. The method of claim 72 wherein said step for processing includes the step of evaluating a set of rules if the length of said first impulse and said second impulse are not equal:

1. when said operation is a Boolean AND operation, said polarity of said longer impulse indicates whether said resultant bit string is a run or an impulse;

2. when said function is a Boolean OR operation, said polarity of said longer impulse indicates whether the resultant bit string is a run or an impulse;

3. when said function is a Boolean EXCLUSIVE OR operation, the resultant bit string is an impulse.

81. The method of claim 71 wherein said step for processing includes the step of evaluating a set of rules if the length of said first impulse, and said second impulse are equal:

1. when said function is either a Boolean AND or Boolean OR operation and the polarity of said first and said second impulses is different, said resultant bit string is a run;

2. when said function is either a Boolean AND or a Boolean OR operation, and the polarity of said first and said second impulses is the same, said resultant bit string is an impulse.

3. when said function is a Boolean EXCLUSIVE OR, said resultant bit string is a run.

82. An apparatus using a computer for efficiently processing an operation on a first and a second impulse to determine a resultant run or impulse, said first and said second impulses comprising a run, said run comprising a string of one or more contiguous bits of a same polarity and each said impulse comprising an ending bit at one end of the contiguous bits having an opposite polarity, said apparatus:

means for comparing said length of said first impulse with said length of said second impulse to determine a minimum length, said minimum length of bits being the length of said resultant run or impulse;

means for determining said binary value of said same binary value bits for said first and said second impulses; and

means for processing a selected operation on said first and said second impulses to determine whether said resultant bit string is a run or an impulse.

83. The apparatus of claim 82 further comprising means for comparing said length of said first impulse with said length of said second impulse to determine whether the length of said first impulse is less than, greater than, or equal to the length of said second impulse.

84. The apparatus of claim 82 further comprising the means for storing said polarity, said type (run or impulse) and said length of one or more of said run or impulses into a temporary memory area and means for combining a plurality of said runs into a single said run.

85. The apparatus of claim 82 or 83 further comprising the means for storing said polarity, said type (run or impulse) and said length of one or more of said run or impulse into a temporary memory area and combining said one or more run or impulse into one or more impulses.

86. The apparatus of claim 82 wherein said means for processing said selected operation further includes the step of forming an index table to determine said selected operation, said index table comprising plurality of said operations.

87. The apparatus of claim 86 wherein said means for forming an index table further comprises means for representing each said operation by one or more subtables, each said subtable comprising a first, a second, and a third index, said first index for identifying a polarity of said first impulse, said second index for identifying a polarity of said second impulse, and said third index for identifying whether the length of said first impulse is less than, greater than, or equal to the length of said second impulse.

88. The apparatus of claim 87 wherein said means for forming said index table further comprises means for referencing said first, said second, and said third indexes to reference said selected operation.

89. The apparatus of claim 82 wherein said means for performing a selected operation further comprises means determining whether said first and said second impulses are equal or unequal in length.

90. The apparatus of claim 82 wherein said means for processing said selected operation further includes means for performing a Boolean operation.

91. The apparatus of claim 83 wherein said means for processing includes the step of evaluating a set of rules if the length of said first impulse and said second impulse are not equal:

1. when said operation is a Boolean AND operation, said polarity of said longer impulse indicates whether said resultant bit string is a run or an impulse;

2. when said function is a Boolean OR operation, said polarity of said longer impulse indicates whether the resultant bit string is a run or an impulse;

3. when said function is a Boolean EXCLUSIVE OR operation, the resultant bit string is an impulse.

92. The apparatus of claim 83 wherein said means for processing includes evaluating a set of rules if the length of said first impulse and said second impulse are equal:

1. when said function is either a Boolean AND or Boolean OR operation and the polarity of said first and said second impulses is different, said resultant bit string is a run;

2. when said function is either a Boolean AND or a Boolean OR operation, and the polarity of said first and said second impulses is the same, said resultant bit string is an impulse.

3. when said function is a Boolean EXCLUSIVE OR, said resultant bit string is a run.

93. A method using a computer for efficiently processing a Boolean operation on a first and a second impulse to determine a resultant bit string, said first and second impulses comprising a run, said run comprising a string of one or more contiguous bits of a same polarity and each said impulse comprising an ending bit at one end of the contiguous bits having a polarity opposite said same polarity, each said impulse encoded in a compressed impulse format, said compressed impulse format comprising at least a first and a second indicator, said first indicator for indicating a polarity of said same polarity bits and said second indicator for indicating a length of said impulse, wherein said length of bits is a quantity of said same polarity bits, said method comprising the steps of:

comparing said length of said first impulse with said length of said second impulse to determine a minimum length, said minimum length being the length of bits for said resultant bit string;

referencing an index table to determine a predefined operation to perform on said first and said second impulses, said index table comprising one or more subtables, each said subtable comprising first, second, and third indexes, said first index for identifying the polarity of said first impulse, said second index for identifying the polarity of said second impulse and said third index for identifying whether said first impulse is less than, greater than or equal to said second impulse, whereby said first, said second, and said third indexes are used to determine which predefined operation to perform;

separate from the prior recited step of referencing, performing said predefined operation on said minimum length of said first and said second impulses to determine the polarity of said resultant bit string and whether said resultant bit string is a run or an impulse;

whereby a method is provided for processing said operation on said first and said second impulses to determine said resultant bit string.

94. The method of claim 93 wherein said predefined operation is a Boolean operation.

95. The method of claim 93 further comprising the step of adding to said quantity of said same polarity bits said opposite polarity bit.

96. The method of claim 93 or 94 further comprising the step of comparing said length of said first impulse with said length of said second impulse to determine whether the length of said first impulse is less than, greater than or equal to the length of said second impulse.

97. The method of claim 96 further comprising the step of appending to said resultant bit string one or more bits of said first impulse, said one or more bits not processed by said operation, and said length for said first impulse being longer than said length of said second impulse and said operation is Boolean OR or Boolean EXCLUSIVE OR operation.

98. The method of claim 96 further comprising the step of appending to said resultant bit string one or more bits of said second impulse, said one or more bits not processed by said operation, and said length of said second impulse being longer than said length of said first impulse and said operation is Boolean OR or Boolean EXCLUSIVE OR operation.

99. The method of claim 96 further comprising the step of truncating one or more bits from said first impulse, said one or more bits not processed by said operation, and said first impulse is longer than said second impulse, and said operation being Boolean AND operation.

100. The method of claim 96 further comprising the step of truncating from said second impulse one or more bit, said one or more bits not processed by said operation, and said second impulse being longer than said first impulse, said operation being Boolean AND operation.

101. An apparatus for use in a computer for efficiently processing a Boolean operation on a first and a second impulse to determine a resultant bit string, said first and second impulses comprising a run, each said run comprising a string of one or more contiguous bits of a same polarity and each said impulse comprising an ending bit at one end of the contiguous bits having a polarity opposite said same polarity, each said impulse encoded in a compressed impulse format, said compressed impulse format comprising at least a first and a second indicator, said first indicator for indicating a polarity of said run and said second indicator for indicating a length in said impulse, wherein said length is a quantity of said same polarity bits and said opposite polarity bit, said apparatus for processing said impulses comprising:

means for comparing said length of said first impulse with said length of said second impulse to determine a minimum length, said minimum length being the length of bits for said resultant bit string;

means for referencing an index table to determine a predefined operation to perform on said first and said second impulses, said index table comprising one or more subtables, each said subtable comprising first, second, and third indexes, said first index for identifying the polarity of said first impulse, said second index for identifying the polarity of said second impulse and said third index for identifying whether said first impulse is less than, greater than or equal to said second impulse, whereby said first, said second, and said third indexes are used

separate from the prior recited means for referencing, means for performing said predefined operation on said minimum length of said first and said second impulses to determine the polarity of said resultant bit string and whether said resultant bit string is a run or an impulse;

whereby an apparatus is provided for processing said operation on said first and said second impulses to determine said resultant bit string.

102. The apparatus of claim 101 wherein said predefined operation is a Boolean operation.

103. The apparatus of claim 101 further comprising means for adding to said quantity of said same polarity bits said opposite polarity bits.

104. The apparatus of claim 101 or 102 further comprising means for comparing said length of said first impulse with said length of bits of said second impulse to determine whether the length of said first impulse is less than, greater than or equal to the length of said second impulse.

105. The apparatus of claim 104 further comprising means for appending to said resultant bit string one or more bits of said first impulse, said one or more bits not processed by said operation, and said length of said first impulse being longer than said length of said second impulse and said operation being Boolean OR or Boolean EXCLUSIVE OR operation.

106. The apparatus of claim 104 further comprising means for appending to said resultant bit string one or more bits of said second impulse, said one or more bits not processed by said operation, and said length of bits of said second impulse being longer than said length of bits of said first impulse length of bits and said operation being Boolean OR or Boolean EXCLUSIVE OR operation.

107. The apparatus of claim 104 further comprising means for truncating one or more bits from said first impulse, said one or more bits not processed by said operation, and said first impulse being longer than said second impulse, and said operation being Boolean AND operation.

108. The apparatus of claim 104 further comprising means for truncating one or more bits from said second impulse, said one or more bits not processed by said operation, and said second impulse being longer than said first impulse, and said operation being Boolean AND operation.

109. A method using a computer for efficiently processing a Boolean operation on a first and a second one-dimensional-compressed-array of binary bits (bit string) and for constructing a resultant-compressed bit string (resultant bit string), said resultant bit string resulting from said Boolean operation, said first and said second bit strings comprising one or more impulses, each said one or more impulses comprising a run, said run comprising a string of one or more contiguous bits of a same polarity and each said one or more impulses comprising an ending bit at one end of the contiguous bits having a polarity opposite said same polarity, each said one or more impulses encoded in a compressed impulse format, said compressed impulse format comprising at least a first and a second indicator, said first indicator for indicating a polarity of said one or more same polarity bits, and said second indicator for indicating a length in said impulse, wherein said length is a quantity of said same polarity bits and said opposite polarity bit, said method comprising the steps of:

comparing said length of a first impulse with said length of bits of a second bit string impulse to determine a minimum length, said minimum length being a length for an intermediate-resultant compressed bit string (intermediate bit string);

determining the polarity of said intermediate bit string and whether said intermediate bit string is a run type or an impulse type;

reducing said length of said first and said second impulses by said minimum length to account for said bits which have been processed by said predefined function;

separate from the prior recited step of reducing, determining whether the length of said first and/or said second impulses has been reduced to zero;

obtaining said polarity and said length for a next impulse of said first and said second bit strings when both said first and said second impulses are reduced to a zero length of bits;

obtaining said polarity and said length for a next impulse of said first or said second bit string which is reduced to a zero length of bits, when either said first or said second impulse is reduced to a zero length of bits; and

performing said prior recited steps until no more impulses reside in said first and said second bit strings, whereby a method is provided for processing said Boolean operation on said first and said second bit strings to construct said resultant bit string.

110. The method of claim 109 further comprising the step of storing said polarity, said length and said type of said intermediate bit string in a temporary memory area until said intermediate bit strings can be represented as one or more said impulses.

111. The method of claim 109 wherein said step for determining includes the step of forming an index table, said index table comprising one or more operations.

112. The method of claim 111 wherein said step for forming said index table further comprises the step of forming one or more subtables, each said subtable comprising first, second, and third indexes, said first index for identifying the polarity of said first impulse, said second index for identifying the polarity of said second impulse and said third index for identifying whether the length of said first impulse is less than, greater than or equal to the length of said second impulse.

113. The method of claim 112 wherein said step for forming said subtable further comprises the step of forming a fourth and a fifth index, said fourth index for identifying said first bit string end-of-bit string condition and said fifth index for identifying said second bit string end-of-bit string condition.

114. The method of claim 112 wherein said step for forming said subtable further comprises the step of forming a signal indicating an end-of-bit string condition in said first and said second bit string.

115. The method of claim 109 further comprising the step of appending to said resultant bit string one or more bits of said first bit string, said one or more bits not processed by said Boolean operation, and said first bit string being longer than said second bit string, and said Boolean operation being an OR or an EXCLUSIVE OR operation.

116. The method of claim 109 further comprising the step of appending to said resultant bit string one or more bits of said second bit string, said one or more bits not processed by said Boolean operation, and said second bit string being longer than said first bit string, and said Boolean operation being an OR or an EXCLUSIVE OR operation.

117. The method of claim 109 further comprising the step of truncating one or more bits from said first bit string, said one or more bits not processed by said Boolean operation, and said first bit string being longer than said second bit string, and said Boolean operation being an AND operation.

118. The method of claim 109 further comprising the step of truncating one or more bits from said second bit string, said one or more bits not processed by said Boolean operation, and said second bit string being longer than said first bit string, and said Boolean operation being an AND operation.

119. The method of claim 110 wherein said step for storing further includes the step of appending one or more bits to said intermediate bit string to form an impulse, said intermediate bit string being the run type.

123. The apparatus of claim 119 wherein said means for forming said index table further comprises means for forming one or more subtables, each said subtable comprising first, second, and third indexes, said first index for identifying the polarity of said first impulse said second index for identifying the polarity of said second impulse and said third index for identifying whether the length of said first impulse is less than, greater than or equal to the length said second impulse.

124. The apparatus of claim 123 wherein said means for forming said subtable further comprises means for forming a fourth and a fifth index, said fourth index for identifying said first bit string end-of-bit-string condition and said fifth index for identifying said second bit string end-of-bit-string condition.

125. The apparatus of claim 123 wherein said means for forming said subtable further comprises means forming an end-of-bit-string condition in said first and/or said second bit string.

120. An apparatus using a computer for efficiently processing a Boolean operation on a first and a second one-dimensional-compressed-array of binary bits (bit string) and said apparatus for constructing a resultant-compressed bit string (resultant bit string), said resultant bit string resulting from said Boolean operation, said first and said second bit strings comprising one or more impulses, each said one or more impulses comprising a run, said run comprising a string of one or more bits of a same polarity and each said one or more impulses comprising an ending bit having a polarity opposite said same polarity, each said one or more impulses encoded in a compressed impulse format, said compressed impulse format comprising at least a first and a second indicator, said first indicator for indicating a polarity of said run and said second indicator for indicating a length in said impulse, wherein said length is a quantity of said same polarity bits and said opposite polarity bit, said apparatus comprising:

means for comparing said length of a first impulse with said length of a second impulse to determine a minimum length, said minimum length being a length for an intermediate-resultant compressed bit string (intermediate bit string);

means for determining the polarity of said intermediate bit string and whether said intermediate bit string is a run type or an impulse type;

means for reducing said length of said first and said second impulses by said minimum length to account for said bits which have been processed by said predefined function;

separate from the prior recited means for reducing, means for determining whether the length of said first and/or said second bit string impulses has been reduced to zero;

means for obtaining said polarity and said length for a next impulse of said first and said second bit strings when both said first and said second bit string impulses are reduced to a zero length;

means for obtaining said polarity and said length for a next impulse of said first or said second bit string which is reduced to a zero length, when either said first or said second bit string impulse is reduced to a zero length of bits; and

means for performing said prior recited steps until no more impulses reside in said first and/or said second bit strings, whereby an apparatus is provided for processing of said Boolean operation on said first and said second bit strings to construct said resultant bit string.

121. The apparatus of claim 120 further comprising:

means for storing said polarity, said length of bits and said type of said intermediate bit string in a temporary memory area until said intermediate bit strings can be represented as one or more said impulses.

122. The apparatus of claim 120 wherein said means for determining includes means for forming an index table, said index table comprising one or more operations.

126. The apparatus of claim 120 further comprises means for appending to said resultant bit string one or more bits of said first bit string, said one or more bits not processed by said Boolean operation and said first bit string being longer than said second bit string, and said Boolean operation being an OR or an EXCLUSIVE OR operation.

127. The apparatus of claim 120 further comprises means for appending to said resultant bit string one or more bits of said second bit string, said one or more bits not processed by said Boolean operation and said second bit string being longer than said first bit string, and said Boolean operation being an OR or an EXCLUSIVE OR operation.

128. The apparatus of claim 120 further comprises means for truncating one or more bits from said first bit string, said one or more bits not processed by said Boolean operation, and said first bit string being longer than said second bit string, and said Boolean operation being an AND operation.

129. The apparatus of claim 120 further comprises means for truncating one or more bits from said second bit string, said one or more bits not processed by said Boolean operation, and said second bit string being longer than said first bit string, and said Boolean operation being an AND operation.

130. The apparatus of claim 120 wherein said means for storing further includes means for appending one or more bits to said intermediate bit string to form an impulse, said intermediate bit string being a run type.

131. A method using a computer for efficiently processing the Boolean operations AND, OR or EXCLUSIVE OR on a first and a said second impulse, said first and second impulses comprising a run, said run comprising a string of one or more contiguous bits of a same polarity and each said impulse comprising an ending bit at one end of the contiguous bits having a binary value opposite said same binary value, each said impulse encoded in a compressed impulse format, said compressed impulse format comprising at least a first and a second indicator, said first indicator for indicating a polarity of said one or more same polarity bits and said second indicator for indicating a length in said impulse, wherein said length of bits is a quantity of said same polarity bits, said method for processing said impulses comprising the steps of:

determining a resultant bit string when said first and said second impulses are unequal in length, said step of determining comprising the steps of;

a) comparing said length of said first impulse with said length of said second impulse to determine which said impulse has a longer length of bits and which said impulse has a shorter length of bits, said shorter length being the length of said resultant bit string;

b) determining the polarity of said longer impulse by referring to said polarity indicator of said longer impulse;

c) determining whether said resultant bit string is an impulse type or a run type, said step for determining comprising the step for evaluating a set of rules;

1) when said Boolean operation is an AND operation, said polarity of said longer impulse indicates whether said resultant bit string is said run type or said impulse type;

2) when said Boolean operation is an OR operation, the complement of said polarity of said longer impulse indicates whether the resultant bit string is said run type or said impulse type;

3) when said Boolean operation is an EXCLUSIVE OR operation, the resultant bit string is said impulse type;

determining a resultant bit string when said first and said second impulses are equal in length, said step of determining comprising the steps of;

a) designating the length of said resultant bit string equal to said length of said first or said second impulse;

b) determining whether said resultant bit string is said impulse type or said run type, said step for determining comprising the step for evaluating a set of rules;

1) when said Boolean operation is either an AND or an OR and the polarity of said first and said second impulses is different, said resultant bit string is said run type;

2) when said Boolean operation is either an AND or an OR and the polarity of said first and said second impulses is the same, said resultant bit string is said impulse type;

3) when said Boolean operation is EXCLUSIVE OR, said resultant bit string is said run type;

whereby a method is provided for processing said Boolean operations, AND, OR, or EXCLUSIVE OR, on said first and said second impulses to determine said resultant bit string.

132. The method of claim 131 further comprising the step of adding to said quantity of said same polarity bits the quantity of said opposite polarity bit.

133. The method of claim 131 further comprising the step of performing said Boolean operation on said first indicator of said first impulse with said first indicator of said second impulse to determine a polarity of said intermediate bit string.

134. The method of claim 131 further comprising the step of comparing said length of said first impulse with said length of said second impulse to determine whether said first and said second impulses have equal or unequal lengths.

135. The method of claim 131 further comprising the step of appending to said resultant bit string one or more bits of said first impulse, said one or more bits not processed by said Boolean operation, and said length of said first impulse being longer than said length of said second impulse, and said Boolean operation being an OR or an EXCLUSIVE OR operation.

136. The method of claim 131 further comprising the step of adding to said resultant bit string one or more bits of said second impulse, said one or more bits not processed by said Boolean operation, and said length of said second impulse being longer than said length of said first impulse, and said Boolean operation being an OR or an EXCLUSIVE OR operation.

137. The method of claim 131 comprising the step of truncating one or more bits from said first impulse, said one or more bits not processed by said Boolean operation, and said first impulse being longer than said second impulse, and said Boolean operation being an AND operation.

138. The method of claim 131 further comprising the step of truncating one or more bits from said second impulse, said one or more bits not processed by said Boolean operation, and said second impulse being longer than said first impulse, and said Boolean operation being an AND operation.

139. An apparatus using a computer for efficiently processing the Boolean operations AND, OR or EXCLUSIVE OR on a first and a said second impulse, each said first and second impulses comprising a run, said run comprising a string of one or more contiguous bits of a same polarity and each said one or more impulses comprising an ending bit at one end of the contiguous bits having a polarity opposite said same polarity, each said impulse encoded in a compressed impulse format, said compressed impulse format comprising at least a first and a second indicator, said first indicator for indicating a polarity of said same binary value bits and said second indicator for indicating a length of bits in said impulse, wherein said length is a quantity of said same polarity bits and said opposite polarity bit, said apparatus for efficiently processing said Boolean operations and for constructing said resultant bit string comprising:

means for determining a resultant bit string when said first and said second impulses are unequal in length, said means for determining comprising;

a) means for comparing said length of said first impulse with said length of said second impulse to determine which said impulse has a longer length of bits and which impulse has a shorter length of bits, said shorter length being the length of said resultant bit string;

b) means for determining the polarity of said longer impulse by referring to said polarity indicator of said longer impulse;

c) means for determining whether said resultant bit string is an impulse type or a run type, said means for determining comprising means for evaluating a set of rules;

1) when said Boolean operation is an AND operation, said polarity of said longer impulse indicates whether said resultant bit string is said run type or said impulse type;

2) when said Boolean operation is an OR operation, the complement of said polarity of said longer impulse indicates whether the resultant bit string is said run type or said impulse type;

3) when said Boolean operation is an EXCLUSIVE OR operation, the resultant bit string is said impulse type;

means for determining a resultant bit string when said first and said second impulses are equal in length, said means for determining comprising the steps;

a) means for designating the length of said resultant bit string equal to said length of said first or said second impulses;

b) means for determining whether said resultant bit string is said impulse type or said run type, said means for determining comprising means for evaluating a set of rules;

1) when said Boolean operation is either an AND or an OR and the polarity of said first and said second impulses is different, said resultant bit string is said run type;

2) when said Boolean operation is either an AND or an OR and the polarity of said first and said resultant bit string is said impulse type;

3) when said Boolean operation is EXCLUSIVE OR, said resultant bit string is said run type;

whereby an apparatus is provided for processing said Boolean operations, AND, OR, or EXCLUSIVE OR, on said first and second impulses to determine said resultant bit string.

140. The apparatus of claim 139 further comprising means for adding to said quantity of said same binary value bits, the quantity of said opposite binary value bit.

141. The apparatus of claim 140 comprising means for performing said Boolean operation on said first indicator of said first impulse with said first indicator of said second impulse to determine a polarity of said intermediate resultant bit string;

142. The apparatus of claim 139 further comprising

for comparing said length of said first impulse with said length said second impulse to determine whether said first and said second impulses have equal or unequal lengths.

143. The apparatus of claim 139 further comprising means for appending to said resultant bit string one or more bits of said first impulse, said one or more bits not processed by said Boolean operation, and said length of said first impulse being longer than said length of said second impulse, and said Boolean operation being an OR or an EXCLUSIVE OR operation.

144. The apparatus of claim 139 further comprising means for appending to said resultant bit string one or more bits of said second impulse, said one or more bits not processed by said Boolean operation, and said length of bits of said second impulse being longer than said length of bits of said first impulse, and said Boolean operation being an OR or an EXCLUSIVE OR operation.

145. The apparatus of claim 139 further comprising means for truncating one or more bits from said first impulse, said one or more bits not processed by said Boolean operation, and said first impulse is longer than said second impulse, and said Boolean operation being an AND operation.

146. The apparatus of claim 139 further comprising means for truncating one or more bits from said second impulse, said one or more bits not processed by said Boolean operation, and said second impulse is longer than said first impulse, and said Boolean operation being an AND operation.

147. A method using a computer for efficiently processing a Boolean operation on a first and a second one-dimensional-compressed-array of binary bits (bit string), said first and said second bit strings comprising one or more impulses, each said one or more impulses comprising a run, said run comprising a string of one or more contiguous bits of a same polarity and each said one or more impulses comprising an ending bit at one end of the contiguous bits having a polarity opposite said same polarity, each said one or more impulses encoded in a compressed impulse format, said compressed impulse format comprising at least a first and a second indicator, said first indicator for indicating a polarity of said one or more same binary value bits and said second indicator for indicating a length in said impulse, wherein said length is a quantity of said same binary value bits, said method for processing said Boolean operation comprising the steps of:

determining an intermediate-resultant-compressed bit string (intermediate bit string) when a first and a second impulse are unequal in length, said step of determining comprising the steps of;

a) comparing said second indicator of said first impulse with said second indicator of said second impulse to determine which said impulse has a longer length and which impulse has a shorter length, said shorter length being the length of said intermediate bit string;

b) determining the polarity of said longer impulse by referring to said first indicator of said longer impulse;

c) determining whether said intermediate bit string is an impulse type or a run type, said step for determining comprising the step of evaluating a set of rules;

1) when said Boolean operation is an AND operation, said polarity of said longer impulse indicates whether said intermediate bit string is said run type or said impulse type;

2) when said Boolean operation is an OR operation, the complement of said polarity of said longer impulse indicates whether the intermediate bit string is said run type or said impulse type;

3) when said Boolean operation is an EXCLUSIVE OR operation, the inter mediate bit string is said impulse type;

determining said intermediate bit string when said first and said second impulses are equal in length, said step of determining comprising the steps of;

a) designating the length of said intermediate bit string equal to said length of said first or said second impulses;

b) determining whether said intermediate bit string is an impulse type or a run type, said step for determining comprising the step of evaluating a set of rules;

1) when said Boolean operation is either an AND or an OR and the polarity of said first and said second impulses is different, said intermediate bit string is said run type;

2) when said Boolean operation is either an AND or an OR and the polarity of said first and said second impulses is the same, said intermediate bit string is said impulse type;

3) When said Boolean operation is EXCLUSIVE OR, said intermediate bit string is said run type; and

performing said Boolean operation on said first indicator of said first impulse with said first indicator of said second impulse to determine a polarity of said intermediate resultant bit string;

performing the previously recited steps on each said impulse in said first and said second bit strings, whereby a method is provided for processing said Boolean operations AND, OR, or EXCLUSIVE OR on said first and said second bit strings.

148. The method of claim 147 further comprising the step of adding to said quantity cf same polarity bits the opposite polarity bits.

149. The method of claim 147 further comprising the step of comparing said length of said first bit string impulse with said length of said second bit string impulse to determine whether said first and said second bit string impulses have equal or unequal lengths.

150. The method of claim 147 further comprising the step of reducing said length of said first and second impulses by said length of said intermediate bit string to account for said bits which have been processed.

151. The method of claim 150 further comprising the step of determining whether said length of said first and/or said second impulses has been reduced to zero length.

152. The method of claim 151 further comprising the step of obtaining said polarity and said length for a next impulse of said first and second bit string when said first and second impulses are reduced to zero length.

153. The method of claim 151 further comprising the step of obtaining said polarity and said length for a next impulse of said first or said second bit string, when said first or second impulse is reduced to a zero length.

154. The method of claim 147 further comprising the step of constructing a resultant bit string, said resultant bit string comprising one or more of said intermediate bit strings, said step of constructing comprising the steps of storing the polarity and the length of said one or more intermediate bit strings into a temporary memory area and combining said one or more intermediate bit strings into one or more impulses of said resultant bit string, whereby a method is provided for processing said Boolean operations, AND, OR, or EXCLUSIVE OR, on said first and said second bit strings and for constructing said resultant:

bit string.

155. The method of claim 147 wherein said step for storing further includes the step of appending one or more bits to said intermediate bit string to form an impulse, said intermediate bit string being the run type.

156. The method of claim 147 further comprising the step of truncating one or more bits from said first bit string, said one or more bits not processed by said Boolean operation, and said first bit string being longer than said second bit string, and said Boolean operation being an AND operation.

157. The method of claim 147 further comprising the step of truncating one or more bits from said second bit string, said one or more bits not processed by said Boolean operation, and said second bit string being longer than said first bit string, and said Boolean operation being an AND operation.

158. The method of claim 147 further comprising the step of appending to said intermediate bit string one or more bits of said first bit string, said one or more bits not processed by said Boolean operation, and said first bit string being longer than said second bit string, and said Boolean operation being an OR or an EXCLUSIVE OR operation.

159. The method of claim 147 further comprising the step of appending to said intermediate bit string one or more bits of said second bit string, said one or more bits not processed by said Boolean operation, and said second bit is longer than said first bit string, and said Boolean operation being an OR or an EXCLUSIVE OR operation.

160. An apparatus using a computer for efficiently processing the Boolean operations AND, OR or EXCLUSIVE OR on a first and a second one-dimensional-compressed-array of binary bits (bit string), said first and said second bit strings comprising one or more impulses, each said one or more impulses comprising a run, said run comprising a string of one or more contiguous bits of a same polarity and each said one or more impulses comprising an ending bit at one end of the contiguous bits having a polarity opposite said same polarity, each said one or more impulses encoded in a compressed impulse format, said compressed impulse format comprising at least a first and a second indicator, said first indicator for indicating a polarity of said one or more same binary value bits and said second indicator for indicating a length in said impulse, wherein said length is a quantity of said same polarity bits, said apparatus for efficiently processing a Boolean operation comprising:

means for determining an intermediate-resultant-compressed bit string (intermediate bit string) when a first and a second impulse are unequal in length, said means for determining comprising;

a) means for comparing said second indicator of said first impulse with said second indicator of said second impulse to determine which said bit string impulse has a longer length and which bit string impulse has a shorter length, said shorter length being the length of said intermediate bit string;

b) means for determining the polarity of said longer impulse by referring to said first indicator of said longer impulse;

c) means for determining whether said intermediate bit string is an impulse type or a run type, said means for determining comprising means for evaluating a set of rules;

1) when said Boolean operation is an AND operation, said polarity of said longer impulse indicates whether the intermediate bit string is said run type or said impulse type;

2) when said Boolean operation is an OR operation, the complement of said polarity of said longer impulse indicates whether the intermediate bit string is said run type or said impulse type;

3) when said Boolean operation is an EXCLUSIVE OR operation, the inter mediate bit string is said impulse type;

means for determining said intermediate bit string when said first and said second impulses are equal in length, said means for determining comprising;

a) means for designating the length of said intermediate bit string equal to said length of said first and said second impulses;

b) means for determining whether said inter mediate bit string is an impulse type or a run type, said means for determining comprising means for evaluating a set of rules;

1) when said Boolean operation is either an AND or an OR and the polarity of said first and said second impulses is different, said intermediate bit string is said run type;

2) when said Boolean operation is either an AND or an OR and the polarity of said first and said second impulses is the same, said intermediate bit string is said

3) when said Boolean operation is EXCLUSIVE OR, said intermediate bit string is said run type;

means for performing said Boolean operation on said first indicator of said first impulse with said first indicator of said second impulse to determine a polarity of said intermediate resultant bit string;

means for performing the previously recited steps on each said impulse in said first and said second bit string, whereby a method is provided for processing said Boolean operations AND, OR, or EXCLUSIVE OR on said first and said second bit strings.

161. The apparatus of claim 160 further comprising means for adding to said quantity of same polarity bits the opposite polarity bit.

162. The apparatus of claim 160 further comprising means for reducing said length of said first and said second impulses by said length of said intermediate bit string to account for said bits which have been processed.

163. The apparatus of claim 162 further comprising means for determining whether said length of said first and/or said second impulses has been reduced to zero length.

164. The apparatus of claim 163 further comprising means for obtaining said polarity and said length for a next impulse of said first and second bit string when said first and second impulse are reduced to zero length.

165. The apparatus of claim 163 further comprising means for obtaining said polarity and said length for said first or said second impulse which is reduced to a nonzero length of bits and means for obtaining said polarity and said length for a next impulse of said first or said second bit string having an impulse which is reduced to zero length.

166. The apparatus of claim 160 a further comprising means for constructing said resultant bit string, said resultant bit string comprising one or more of said intermediate bit strings, said means for constructing comprising means for storing the polarity and the length of said one or more intermediate bit strings into a temporary memory area and means for combining said one or more intermediate bit strings into one or more impulses of said resultant bit strings.

167. The apparatus of claim 166 wherein said means for storing further includes means for appending one or more bits to said intermediate bit string to form one or more impulses, said intermediate bit string being the run type.

168. The apparatus of claim 160 further comprising means for truncating one or more bits from said first bit string, said one or more bits not processed by said Boolean operation, and said first bit string being longer than said second bit string, and said Boolean operation being an AND operation.

169. The apparatus of claim 160 further comprising means for truncating one or more bits from said second bit string, said one or more bits not processed by said Boolean operation, and said second bit string being longer than said first bit string, and said Boolean operation being an AND operation.

170. The apparatus of claim 160 further comprising means for appending to said intermediate bit string one or more bits of said first bit string, said one or more bits not processed by said Boolean operation, and said first bit string being longer than said second bit string, and said Boolean operation being an OR or an EXCLUSIVE OR operation.

171. The apparatus of claim 160 further comprising means for appending to said intermediate bit string one or more bits of said second bit string, said one or more bits not processed by said Boolean operation, and said second bit being longer than said first bit string, and said Boolean operation being an OR or an EXCLUSIVE OR operation.

172. A method using a computer for efficiently processing a Boolean operation on a first and a second run, said first and said second runs comprising a string of one or more contiguous bits of a same polarity, each said run encoded in a compressed format, said compressed format comprising at least a first and a second indicator, said first indicator for indicating a polarity of said one or more same polarity bits and said second indicator for indicating a length of bits in said run, wherein said length is a quantity of said same polarity bits, said method for processing said runs comprises the steps of:

determining a resultant bit string when said first and said second bit string runs are unequal in length, said step of determining comprising the step comparing said length of said first run with said length of bits of said second run to determine which said run has a longer length and which said run has a shorter length, said shorter length being the length of said resultant bit string;

determining a resultant bit string when said first and said second runs are equal in length, said step of determining comprising the step designating the length of said resultant bit string equal to said length of said first or said second run;

determining the polarity of said resultant bit string by performing said Boolean operation on said first indicator of said first run with said first indicator of said second run.

173. The method of claim 172 further comprising the step of comparing said length of said first run with said length of bits of said second run to determine whether said first and said second runs have equal or unequal bit lengths.

174. The method of claim 172 further comprising the step of appending to said resultant bit string one or more bits of said first run, said one or more bits not processed by said Boolean operation, and said length of said first run being longer than said length of said second run, and said Boolean operation being an OR or an EXCLUSIVE OR operation.

175. The method of claim 172 comprising the step of truncating one or more bits from said first run, said one or more bits not processed by said Boolean operation, and said first run being longer than said second run, and said Boolean operation being an AND operation.

176. An apparatus using a computer for efficiently processing a Boolean operation on a first and a second run, said first and second runs comprising a string of one or more contiguous bits of a same polarity, each said run encoded in a compressed format, said compressed format comprising at least a first and a second indicator, said first indicator for indicating a polarity of said same polarity bits and said second indicator for indicating a length of bits in said run, wherein said length is a quantity of said same polarity bits and said opposite polarity bit, said apparatus for efficiently processing said runs comprising:

means for determining a resultant bit string when said first and said second runs are unequal in length, said means for determining comprising means for comparing said length of said first impulse with said length of said second impulse to determine which said run has a longer length and which run has a shorter length, said shorter length being the length of said resultant bit string;

means for determining a resultant bit string when said first and said second runs are equal in length, said means for determining comprising the step means for designating the length of said resultant bit string equal to said length of said first or said second runs;

means for determining the polarity of said resultant bit string by performing said Boolean operation on said first indicator of said first run with said first indicator of said second run.

177. The apparatus of claim 176 further comprising means for comparing said length of bits of said first run with said length of bits of said second run to determine whether said first and second runs have equal or unequal bit lengths.

178. The apparatus of claim 176 further comprising means for appending to said resultant bit string one or more bits of said first run, said one or more bits not processed by said Boolean operation, and said length of said first run being longer than said length of said second run, and said Boolean operation being an OR or an EXCLUSIVE OR operation.

179. The apparatus of claim 176 further comprising means for truncating one or more bits from said first run, said one or more bits not processed by said Boolean operation, and said first run is longer than said second run, and said Boolean operation being an AND operation.