國立高雄大學圖資館 |

Language: English

Back

Coding for general penalties.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Coding for general penalties.
Author:	Baer, Michael Byron.
Description:	118 p.
Notes:	Adviser: Thomas M. Cover.
Notes:	Source: Dissertation Abstracts International, Volume: 64-05, Section: B, page: 2309.
Contained By:	Dissertation Abstracts International64-05B.
Subject:	Engineering, Electronics and Electrical.
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3090553
ISBN:	0496382756

Coding for general penalties.
Baer, Michael Byron.

Coding for general penalties. [electronic resource] - 118 p.

Adviser: Thomas M. Cover.

Thesis (Ph.D.)--Stanford University, 2003.

Huffman coding finds a prefix-free code that minimizes the expected codeword length for a probability mass function. However, there are many practical situations in which the constraints and goals may be different from the linear penalty of minimizing expected length. For example, we may wish to avoid long codewords in some situations, since these may cause an excessive wait for transmission of unlikely events. Therefore, we may desire a nonlinear penalty in the codeword lengths. Such penalties arise naturally in group testing for diagnostic systems, queueing, remote exploration, and military intelligence.

ISBN: 0496382756Subjects--Topical Terms:

226981
Engineering, Electronics and Electrical.

Coding for general penalties.
LDR:02726nmm _2200277 _450 001 161979
005 20051017073357.5
008 230606s2003 eng d
020 $a 0496382756
035 $a 00148480
035 $a 161979
040 $a UnM $c UnM
100 0 $a Baer, Michael Byron. $3 227077
245 1 0 $a Coding for general penalties. $h [electronic resource]
300 $a 118 p.
500 $a Adviser: Thomas M. Cover.
500 $a Source: Dissertation Abstracts International, Volume: 64-05, Section: B, page: 2309.
502 $a Thesis (Ph.D.)--Stanford University, 2003.
520 # $a Huffman coding finds a prefix-free code that minimizes the expected codeword length for a probability mass function. However, there are many practical situations in which the constraints and goals may be different from the linear penalty of minimizing expected length. For example, we may wish to avoid long codewords in some situations, since these may cause an excessive wait for transmission of unlikely events. Therefore, we may desire a nonlinear penalty in the codeword lengths. Such penalties arise naturally in group testing for diagnostic systems, queueing, remote exploration, and military intelligence.
520 # $a We examine families of coding problems with nonlinear penalties. These include generalizations of Huffman coding suitable for communication and analysis, extending instances of source coding found in the literature. Alternative penalty measures previously considered include exponential average and maximal pointwise redundancy. We find a novel framework encompassing these two penalties, as well as the linear and other natural penalties, resulting in properties and algorithms suitable for all of them.
520 # $a We next turn to generalized quasilinear convex penalties; these are penalties that can be formulated as Sigmai f ( li, pi), where li denotes the length of the ith codeword, pi denotes the corresponding probability, and f is convex and increasing in li. This class of penalties includes several previously proposed penalties, among them a general convex problem proposed by Campbell. We give an efficient algorithm that, for Campbell's problem, performs the optimization in quadratic time and linear space; we also present penalty bounds for this solution. Finally, we consider coding for infinite alphabets, a problem not fully understood even for the linear penalty.
590 $a School code: 0212.
650 # 0 $a Engineering, Electronics and Electrical. $3 226981
650 # 0 $a Computer Science. $3 212513
710 0 # $a Stanford University. $3 212607
773 0 # $g 64-05B. $t Dissertation Abstracts International
790 $a 0212
790 1 0 $a Cover, Thomas M., $e advisor
791 $a Ph.D.
792 $a 2003
856 4 0 $u http://libsw.nuk.edu.tw/login?url=http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3090553 $z http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3090553