Concurrent detection of errors in arithmetic data compression coding
AssigneeInternational Business Machines Corporation
InventorsRonald B. Arps, Ehud D. Karnin
Life of this patent
Estimating the term…
Abstract
Method and means for detecting any single errors introduced into an arithmetic data compression code string as a result of coding, transmission, or decoding through testing according to a modulo-n function, n being an odd number not equal to +1 or -1, an arithmetic compression coded data stream C'(s) genmerated by n-scaling an arithmetically recursive function that produces a non-scaled arithmetically data compressed code stream C(s) as a number in the semi-open coding range [0,1].
Claims14
A method for detecting single-bit errors during the recursive machine encoding of a binary symbol string s=b(1), b(2), . . . , b(i), . . . , b(n) to produce a compressed binary number c(s) as a representation of s, c(s) being a number in the semi-open interval [0,1], the interval being successively subdivided during successive encoding cycles, each subinterval being defined by its lower bound c(s) and a variable a(s) such that [c(s), c(s)+a(s)];
- the values of c(s) and a(s) being computed as arithmetically recursive functions of c(s) and a(s), comprising the steps of:
- scaling the arithmetically recursive functions by n, n being an odd number not equal to + or -1;
- transforming s into a compressed error encoded binary representation C'(s) in the semi-open interval ([0,n] according to said n-scaled arithmetically recursive functions;
- and
- testing C'(s) by a modulo-n function for a non-zero residue.
A method for detecting single-bit errors during the recursive machine modification of a string C(s) of binary numbers to produce C(si) where C(si) is a compressed representation of an m-ary symbol stream s=m(1), m(2), . . . , m(i), . . . and is responsive to the next symbol m(i) in s, C(si) being a number in the semi-open coding range [0,1], the coding range being subdivided into intervals during successive machine string modification cycles, each interval being defined by its lower bound C(s) and an interval parameter A(s) such that (C(s), C(s)+A(s)), said method being executable on a pair of binary registers C and A, each having a finite dimension, w, comprising the steps of:
- placing initial contents in registers A and C;
- for the next symbol m(i) in the string s, reading in a coding variable corresponding to the conditional probability of m(i) at its location in the string s;
- scaling said coding variable by n, n being an odd number not equal to + or -1;
- altering the contents of C and A based upon said scaled coding variable and shifting the contents of C and A in a predetermined direction;
- and
- testing the contents of C by means of a modulo-n function for a non-zero residue.
In an arithmetic encoder of the type responsive to an m-ary symbol string s=m(1), m(2), . . . , m(1), . . . and to coding variable values representing the conditional probabilities of the symbols of s at their locations in s that produces an arithmetically-encoded representation C(s), C(s) being a number in a semi-open coding range between 0 and 1, said encoder including a binary register C for containing the working end of the portion of C(s) resulting from the encoding of the portion of s preceding the next symbol m(i), a binary register A for containing a normalizing factor, and an arithmetic logic means responsive to the coding parameter for the next symbol m(i) for numerically adjusting the contents of C and A based on the conditional probability of m(i) at its position in s and for shifting the contents of C and A in a predetermined magnitude direction based on the adjusted contents of A, such that C(s) includes the successive shifted contents of C, the improvement comprising:
- means for scaling the coding variable value for m(i) by n, n being an odd number not equaling + or -1;
- and
- modulo means for testing the contents of C according to a modulo-n function for a non-zero residue.
In an arithmetic decoder of the type which receives an arithmetically-compressed binary symbol string and generates therefrom successive symbols b(i) of a binary symbol string s=b(1), . . . , b(i), . . . , b(n) by generating a trial coding variable based upon a coding parameter (k), arithmetically testing the trial coding variable against the w most significant bits of the compressed string, and decoding the next symbol b(i) of the string s based upon the outcome of the testing, wherein the arithmetically compressed binary symbol string C'(s) is a number in a semi-open interval between 0 and n, n being an odd number not equal to + or -1, the improvement comprising:
- means for scaling the trial augend by n;
- and
- modulo means for testing C'(s) prior to the generation of b(i).
Dependencies are inferred from the claim text.