DocumentCode
3146154
Title
An optimal algorithm for the construction of optimal prefix codes with given fringe
Author
De Santis, Alfredo ; Persiano, Giuseppe
Author_Institution
Dipartimento di Inf. ed Applicazioni, Salerno Univ., Italy
fYear
1991
fDate
8-11 Apr 1991
Firstpage
297
Lastpage
306
Abstract
The codeword lengths of a maximal prefix code with minimum length among those with a given number of codewords differ by at most one. This paper studies the length of the optimal maximal prefix code with a given number N of codewords and the additional constraint that the difference of the lengths of the longest and shortest codeword must be equal to a given parameter Δ. An optimal algorithm is given that, for all N and Δ, constructs an (N ,Δ)-MPC of minimum length. Then a lower bound is given for the length of the optimal (N ,Δ)-MPC for Δ⩽N /2
Keywords
codes; optimal systems; codeword lengths; minimum length; optimal algorithm; optimal maximal prefix code; Binary codes; Decoding; Terminology;
fLanguage
English
Publisher
ieee
Conference_Titel
Data Compression Conference, 1991. DCC '91.
Conference_Location
Snowbird, UT
Print_ISBN
0-8186-9202-2
Type
conf
DOI
10.1109/DCC.1991.213351
Filename
213351
Link To Document