GRAPH THEORETIC PREFIX CODES AND THEIR SYNCHRONIZING PROPERTIES

被引：6

作者：

BOBROW, LS

HAKIMI, SL

机构：

[1] Department of Electrical Engineering, University of Massachusetts, Amherst

[2] Department of Electrical Engineering, Northwestern University, Evanston

来源：

INFORMATION AND CONTROL | 1969年 / 15卷 / 01期

关键词：

D O I：

10.1016/S0019-9958(69)90641-X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper presents a study of a class of D-nary exhaustive prefix codes which are generated by graphs. In addition to its use as the representation of a code, the structure of a graph is utilized for decoding purposes. The concept of the inclusion property is introduced, and an algorithm for the construction of an inclusion code equivalent to any specified exhaustive prefix code is given. it is shown that the inclusion property is a sufficient condition for a code to have an equivalent graph theoretic realization. Such a graph, which will always have less branches than the tree representation of the code, can be found easily. It is demonstrated that exhaustive variable-length inclusion codes are neither anagrammatic nor uniformly composed. Therefore, a necessary and sufficient condition for such codes to be self-synchronizable is g.c.d. (lengths) = 1. © 1976 Academic Press, Inc.

引用

页码：70 / &

共 21 条

[1]

ASH R, 1965, INFORMATION THEORY

[2]

BOBROW LS, 1968, THESIS NORTHWESTERN

[3]

BREDESON JG, 1967, IEEE T INFORM THEORY, VIT13, P348

[4]

Dewey G., 1923, RELATIVE FREQUENCY E

[5]

FANO RM, 1961, TRANSMISSION INFORMA

[6]

FRAZER WD, 1964, 2 P ALL C CIRC SYST

[7] VARIABLE-LENGTH BINARY ENCODINGS [J].

GILBERT, EN ;

MOORE, EF .

BELL SYSTEM TECHNICAL JOURNAL, 1959, 38 (04) :933-967

[8]

HAKIMI SL, 1968, IEEE T INFORM THEORY, VIT14, P584

[9]

HAKIMI SL, 1965, IEEE T INFORMATION T, VIT11, P457

[10] A METHOD FOR THE CONSTRUCTION OF MINIMUM-REDUNDANCY CODES [J].

HUFFMAN, DA .

PROCEEDINGS OF THE INSTITUTE OF RADIO ENGINEERS, 1952, 40 (09) :1098-1101

← 1 2 3 →