Fast adaptive coding algorithm (Q2277426): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Boris Ya. Ryabko / rank | |||
Property / reviewed by | |||
Property / reviewed by: Q701619 / rank | |||
Property / author | |||
Property / author: Boris Ya. Ryabko / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Ren-ji Tao / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 07:34, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fast adaptive coding algorithm |
scientific article |
Statements
Fast adaptive coding algorithm (English)
0 references
1990
0 references
This paper proposed an adaptive variable-length source coding algorithm, so-called ``frequency coding''. For any message word \(x_ 1...x_ N\) over an alphabet \(A=\{a_ 1,...,a_ n\},\) denoting \(x_{-kn-h+1}=a_ h\), \(k\geq 0\), \(1\leq h\leq n\), the encoder encodes the symbol \(x_ i\) into the first \(m(x_ i,i)\) digits of the binary code of \(Q(x_ i,i)\), concatenating the result onto previous output, where \(\ell =\lceil \log n\rceil,\) \(w=(2^ r-1)2^{\ell},\) \(m(a_ j,i)=1+r+\ell -\lfloor \log (P(a_ j,i)+1)\rfloor,\) \(Q(a_ j,i)=2\sum^{j-1}_{k=1}(P(a_ k,i)+1)+P(a_ j,i)+1,\) and P(a,i) is the number of occurrences of a in \(x_{i-w}x_{i-w+1}...x_{i-1}.\) It is proven in this paper that, for this coding algorithm, redundances are not greater than O(1) as well as time complexities of encoding and of decoding are not greater than \(O(\log^ 2 n)\).
0 references
adaptive variable-length source coding algorithm
0 references
frequency coding
0 references
redundances
0 references
time complexities
0 references