US4044347A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Variable-length to fixed-length conversion of minimum-redundancy codes
Assignee: International Business Machines Corp
•
Filing: 1975-05-19
•
Granted: 1977-08-23
•
Expires: 1995-05-19
Abstract
Abstract Apparatus for converting the codewords of variable-length minimum-redundancy codes into corresponding fixed-length characters. The conversion process employs a two-step mapping wherein a codeword is first converted into a fixed-length integer, and then the integer is used to index a table of fixed-length characters. The apparatus for achieving this two-step mapping comprises table storage, summation circuitry, compare/combine circuitry, and control circuitry. The table storage holds two tables, a first table containing the fixed-length characters and a second table whose values uniquely identify the variable-length code. The compare/combine circuitry and the summation circuitry accept as input the successive bits of a codeword to be converted into its corresponding fixed-length character. As the successive codeword bits are received, the summation circuitry operates on elements of the second table to calculate successive values of a weighted sum and an unweighted sum. The compare/combine circuitry uses the successive values of the weighted sum to isolate the bits comprising the codeword. This codeword is then combined with the weighted sum and the unweighted sum to provide a fixed-length integer, and the integer is used to index the table of fixed-length characters.
Inventors
- 👤 David Curtis Van Voorhis
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 15:50
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42; H03M7/425; H03M7/4025
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
174 words
Apparatus for converting the code words of variable length codes into corresponding fixed-length characters, comprising: a table storage for storing two tables, a first table containing the fixed-length characters, and a second table whose values s(1), s(2), . . . uniquely identify the variable length code; summation circuitry including means operative as the successive code word bits are received to calculate from elements of the second table successive values of a weighted sum t(1), t(2), . . . and an unweighted sum b(1), b(2), . . . according to the relation: ##EQU7## compare/combine circuitry adapted to accept as input the successive bits of a code word to be converted into its corresponding fixed character, connected to said summation circuitry, responsive to the successive values of said weighted sum to isolate the bits comprising the code word; said compare/combine circuitry further including means for adding said code word to the unweighted sum and subtracting the weighted sum to provide a fixed-length integer; and means responsive to said integer to index said table of fixed-length characters.
Claim 2
Dependent Claim
174 words
Apparatus for converting the code words of variable length codes into corresponding fixed-length characters, comprising: a table storage for storing two tables, a first table containing the fixed-length characters, and a second table whose values s(1), s(2), . . . uniquely identify the variable length code; summation circuitry including means operative as the successive code word bits are received to calculate from elements of the second table successive values of a weighted sum t(1), t(2), . . . and an unweighted sum b(1), b(2), . . . according to the relation: ##EQU7## compare/combine circuitry adapted to accept as input the successive bits of a code word to be converted into its corresponding fixed character, connected to said summation circuitry, responsive to the successive values of said weighted sum to isolate the bits comprising the code word; said compare/combine circuitry further including means for adding said code word to the unweighted sum and subtracting the weighted sum to provide a fixed-length integer; and means responsive to said integer to index said table of fixed-length characters.
Claim 3
Dependent Claim
178 words
Apparatus for converting the code words of variable-length codes into corresponding fixed-length characters, comprising: a table storage for storing a first table containing the fixed-length characters and a second table whose contents s(1), s(2), . . . uniquely identify the variable-length code; compare/combine circuitry connected to receive successive bits of a code word to be converted into a corresponding fixed-length character; summation circuitry connected to said table storage, adapted to respond as said successive code word bits are received to operate on stored elements of said second table to calculate successive values of a weighted sum t(1), t(2), . . . and an unweighted sum b(1), b(2), . . . according to the relation: ##EQU8## means connecting said summation circuitry to said compare/combine circuitry; means in said compare/combine circuitry responsive to said weighted sum to isolate bits comprising said code word; and means in said compare/combine circuitry connected to said table storage for adding said code word to said unweighted sum nd subtracting the weighted sum to provide a fixed-length integer for use in indexing said first table.
Claim 4
Dependent Claim
178 words
Apparatus for converting the code words of variable-length codes into corresponding fixed-length characters, comprising: a table storage for storing a first table containing the fixed-length characters and a second table whose contents s(1), s(2), . . . uniquely identify the variable-length code; compare/combine circuitry connected to receive successive bits of a code word to be converted into a corresponding fixed-length character; summation circuitry connected to said table storage, adapted to respond as said successive code word bits are received to operate on stored elements of said second table to calculate successive values of a weighted sum t(1), t(2), . . . and an unweighted sum b(1), b(2), . . . according to the relation: ##EQU8## means connecting said summation circuitry to said compare/combine circuitry; means in said compare/combine circuitry responsive to said weighted sum to isolate bits comprising said code word; and means in said compare/combine circuitry connected to said table storage for adding said code word to said unweighted sum nd subtracting the weighted sum to provide a fixed-length integer for use in indexing said first table.
Claim 5
Dependent Claim
245 words
Apparatus for converting the code words of a variable-length code C V into corresponding fixed-length characters C F , comprising: a table storage for storing a first table containing the fixed-length characters and a second table whose contents s(1), s(2), . . . uniquely identify the variable-length code; compare/combine circuitry connected to receive successive bits y 1 , Y 2 , . . . of a codeword C V (i) to be converted into a corresponding fixed-length character; summation circuitry connected to said table storage adapted to respond as said successive code word bits are received to operate on stored elements of said second table to calculate successive values of weighted sums t(1), t(2) . . . and unweighted sum b(1), b(2), . . . according to the relations: ##EQU9## means connecting said summation circuitry to said compare/combine circuitry; means in said compare/combine circuitry responsive to said weighted sum to isolate bits comprising said code word by comparing the successive codeword bits Y 1 , Y 2 , . . . with successive values of the weighted sum t(1), t(2), . . . until a value t(k) is found to exceed the corresponding k-bit integer y(k)=Y.sub.1 Y.sub.2 Y.sub.3 . . . Y.sub.k comprising k accumulated codeword bits; and means in said compare/combine circuitry connected to said table storage for combining said weighted sum and said unweighted sum with said isolated code word to calculate a fixed-length integer i=y(k)-t(k)+b(k) for use in indexing said first table.
Claim 6
Dependent Claim
245 words
Apparatus for converting the code words of a variable-length code C V into corresponding fixed-length characters C F , comprising: a table storage for storing a first table containing the fixed-length characters and a second table whose contents s(1), s(2), . . . uniquely identify the variable-length code; compare/combine circuitry connected to receive successive bits y 1 , Y 2 , . . . of a codeword C V (i) to be converted into a corresponding fixed-length character; summation circuitry connected to said table storage adapted to respond as said successive code word bits are received to operate on stored elements of said second table to calculate successive values of weighted sums t(1), t(2) . . . and unweighted sum b(1), b(2), . . . according to the relations: ##EQU9## means connecting said summation circuitry to said compare/combine circuitry; means in said compare/combine circuitry responsive to said weighted sum to isolate bits comprising said code word by comparing the successive codeword bits Y 1 , Y 2 , . . . with successive values of the weighted sum t(1), t(2), . . . until a value t(k) is found to exceed the corresponding k-bit integer y(k)=Y.sub.1 Y.sub.2 Y.sub.3 . . . Y.sub.k comprising k accumulated codeword bits; and means in said compare/combine circuitry connected to said table storage for combining said weighted sum and said unweighted sum with said isolated code word to calculate a fixed-length integer i=y(k)-t(k)+b(k) for use in indexing said first table.
Claim 7
Dependent Claim
55 words
The combination according to claim 3 wherein the length L V (i) of the codeword C V (i) representing the ith most frequently occurring fixed-length character is equal to the length of the Huffman codeword for this character, and wherein the codeword C V (i) is the L V (i)-bit binary integer with value ##EQU10##
Claim 8
Dependent Claim
26 words
The combination according to claim 3 wherein the kth tabular value s(k) is the number of k-bit codewords in the variable-length minimum-redundancy code C V .
Claim 9
Dependent Claim
26 words
The combination according to claim 5 wherein the kth tabular value s(k) is the number of k-bit codewords in the variable-length minimum-redundancy code C V .
Claim 10
Dependent Claim
37 words
The combination according to claim 3 wherein the weighted sums t(1), t(2), . . . and the unweighted sums b(1), b(2), . . . are calculated according to the formulas t(1)=b(1)=s(1) t(k)=2t(k-1)+s(k), for k>1 b(k)=b(k-1)+s(k), for k>1
Claim 11
Dependent Claim
37 words
The combination according to claim 4 wherein the weighted sums t(1), t(2), . . . and the unweighted sums b(1), b(2), . . . are calculated according to the formulas t(1)=b(1) t(k)=2t(k-1)=s(k), for k>1 b(k)=b(k-1)+s(k), for k>1
Claim 12
Dependent Claim
37 words
The combination according to claim 5 wherein the weighted sums t(1), t(2), . . . and the unweighted sums b(1), b(2), . . . are calculated according to the formulas t(1)=b(1)=s(1) t(k)=2t(k-1)+s(k), for k>1 b(k)=b(k-1)+s(k), for k>1
Claim 13
Dependent Claim
20 words
The combination according to claim 3 wherein the ith tabular value f(i) is the ith most frequently occurring fixed-length character.
Claim 14
Dependent Claim
20 words
The combination according to claim 4 wherein the ith tabular value f(i) is the ith most frequently occurring fixed-length character.
Claim 15
Dependent Claim
20 words
The combination according to claim 5 wherein the ith tabular value f(i) is the ith most frequently occurring fixed-length character.
Claim 16
Dependent Claim
20 words
The combination according to claim 6 wherein the ith tabular value f(i) is the ith most frequently occurring fixed-length character.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1980-08-22 | 1981-02-21 | 1981-08-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1984-08-22 | 1985-02-21 | 1985-08-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1988-08-22 | 1989-02-21 | 1989-08-23 | $7700.00 | Window Closed / Lapsed |