Browse Prior Art Database

Self Adaptive Compression and Expansion

IP.com Disclosure Number: IPCOM000080498D
Original Publication Date: 1973-Dec-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 3 page(s) / 72K

Publishing Venue

IBM

Related People

Elam, RR: AUTHOR [+3]

Abstract

This is a method and apparatus for adaptively compressing and expanding digital information that exhibits a piecewise linear structurer, using a linear feedback shift register. With reference to the principles of the Massey algorithm, a unique minimum length linear feedback shift register, (LFSR), can be found for any one-zero sequence (S) of length j. The LFSR that is capable of reproducing the sequence S, is specified by an initial loading vector L of length r plus a connective vector C. Vector C is the coefficients of a connective polynomial C(D)=C(0)+C(1)D+ +C(2)D/2/+C(r)D/r/, where C(0) is always one (L) and C(1) ... C(r) can be either zero (0) or one (1) and D is a variable. Therefore, the connective vector C, although being r+1 bits in length, can be specified by r variable bits.

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

Page 1 of 3

Self Adaptive Compression and Expansion

This is a method and apparatus for adaptively compressing and expanding digital information that exhibits a piecewise linear structurer, using a linear feedback shift register. With reference to the principles of the Massey algorithm, a unique minimum length linear feedback shift register, (LFSR), can be found for any one-zero sequence (S) of length j. The LFSR that is capable of reproducing the sequence S, is specified by an initial loading vector L of length r plus a connective vector C. Vector C is the coefficients of a connective polynomial C(D)=C(0)+C(1)D+ +C(2)D/2/+C(r)D/r/, where C(0) is always one (L) and C(1) ... C(r) can be either zero (0) or one (1) and D is a variable. Therefore, the connective vector C, although being r+1 bits in length, can be specified by r variable bits.

Timing and synthesis control 15 has outputs labeled set C(0)=1, set B(1)=1, and SWITCH connected to generator 11. Outputs labeled SHIFT and RESET are connected to input terminals of generator 11 and input of terminals of n- Counter 13. Control 15 furthermore has an output labeled CONTROL TRANSFER for controlling the transfer of the polynomials C(D) and B(D) between registers within the synthesis generator, in order to accomplish correct execution of the compaction algorithm. Outputs labeled R-Control and BR- Control are used for setting switches in the synthesis generator 11, such that hardware constructed with RMAX stages in the registers of synthesis generator 11 can be set to a limit stop R, less than or equal to RMAX. Output 47 labeled SHIFT BUFFER TO LEFT/RIGHT is connected to sequence buffer 41 for appropriately shifting the sequence back and forth, to manipulate the sequence S and insure proper executions of adequate steps.

Input R receives the limit stop variable R and another input d receives the discrepancy signal d from generator 11. Input 16 receives the count n from n- Counter 13 and input 18 receives an overflow signal, which will initiate the limit stop operation the next time a discrepancy value of 1 appears on the line labeled
d. Control 15 also has the capability to produce the value r from count n and the initial signal, which will initiate the limit stop operation the next time a discrepancy value of 1 appears on the line labeled d. Control 15 also has the capability to produce the value r from count n and the initial value r from adequate algorithm steps. Control 15 has a load r bits output connected to the generator 11 and a first input to AND gate 19....