Perturbation Codes: A New Class of Linear Convolutional Codes

点击翻译按钮获取中文摘要

Abstract for NSF Proposal 0830381Project Title: Perturbation Codes: A New Class of LinearConvolutional CodesLinear convolutional codes are widespread in data communication systems and datastorage systems. Each such code processes data at a ¯xed rate and with a ¯xed delay, so thatthe fraction of errors (called average distortion) in the reconstructed data will be acceptablysmall. The primary problem of linear convolutional code design is to ¯nd an optimal code,which is a code yielding the minimum average distortion among codes in a ¯nite set of feasiblecodes. In most cases, with past techniques, this problem could only be solved approximately,yielding an almost optimal code (a code with near minimum average distortion), the set offeasible codes being too large for the average distortion of codes to be examined individually.In this project, we investigate a new technique, called perturbation theory, which reduces theset of feasible codes to a much smaller set of codes called perturbation codes. In many cases,an optimal code will be one of the perturbation codes, and it can be found in a reasonableamount of time.Each linear convolutional code in the set of feasible codes is described via a parity checkmatrix over the binary ¯eld, consisting of a ¯xed number of rows and columns. A perturba-tion class of codes consists of codes whose parity check matrices can be arranged so that acertain number of rows at the top remain ¯xed. Any code will lie in more than one pertur-bation class of codes, depending upon which rows of the parity check matrix are held ¯xed.Under certain conditions, there will be a natural group acting on the parity check matricesof a perturbation class of codes. Using the group structure, a subset of each perturbationclass of codes is selected. A code will be declared to be a perturbation code if it is among theselected codes in a certain number of perturbation classes containing the code. There is °ex-ibility in the de¯nition of perturbation code. In this project, we investigate how to properlydelineate the perturbation code concept so that an optimal code can be found from amonga small set of perturbation codes, for source and channel models of su±cient symmetry.