INFORMATION COMPRESSION AND VARSHAMOV-GILBERT BOUND

被引：1

作者：

KRICHEVSKY, RE

机构：

[1] Acad of Sciences of the USSR, Novosibirsk, USSR, Acad of Sciences of the USSR, Novosibirsk, USSR

来源：

INFORMATION AND COMPUTATION | 1987年 / 74卷 / 01期

关键词：

CODES; SYMBOLIC - Error Correction - COMPUTER METATHEORY - Programming Theory - INFORMATION THEORY - Data Compression;

D O I：

10.1016/0890-5401(87)90008-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The program complexity to enumerate a finite set of words is found. The complexity is either an exponential or a linear function of the word length depending on whether the redundancy is either less or more than 100%. A corollary: the Varshamov-Gilbert bound of the group error correcting code cardinality is tight for almost any channel with additive noise. The proofs are based on the concept of the collision index.

引用

页码：1 / 14

页数：14

共 18 条

[1]

COVER TM, 1973, IEEE T INFORM THEORY, V18, P73

[2]

DEZA ME, 1965, PROBL PEREDACHI INF, V1, P29

[3] ON THE SIZE OF SEPARATING SYSTEMS AND FAMILIES OF PERFECT HASH FUNCTIONS [J].

FREDMAN, ML ;

KOMLOS, J .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1984, 5 (01) :61-68

[4] STORING A SPARSE TABLE WITH O(1) WORST CASE ACCESS TIME [J].

FREDMAN, ML ;

KOMLOS, J ;

SZEMEREDI, E .

JOURNAL OF THE ACM, 1984, 31 (03) :538-544

[5]

FRIEDMAN J, 1984, P 25 S FDN COMP SCI, P506

[6]

Goppa V. D, 1982, IZV AKAD NAUK SSSR M, V46, P762

[7]

GOPPA VD, 1974, PROBLEMY PEREDACHI I, V10, P118

[8]

Khasin L. S., 1970, Soviet Physics - Doklady, V14, P1149

[9]

Knuth D. E., 1973, ART COMPUTER PROGRAM

[10]

Knuth Donald E, 1968, ART COMPUTER PROGRAM, V1

← 1 2 →