Perturbation Codes: A New Class of Linear Convolutional Codes

摘要NSF提案0830381项目名称：扰动码：一类新的线性卷积码线性卷积码广泛应用于数据通信系统和数据存储系统。每一个这样的编码都以固定的速率和固定的延迟处理数据，因此在重构数据中的误差部分（称为平均失真）将是可以接受的小。线性卷积码设计的主要问题是寻找一个最佳码，即在一组可行码中，使各码的平均失真最小的码。在大多数情况下，与过去的技术，这个问题只能近似地解决，产生一个几乎最优的代码（一个代码与附近的最小平均失真），设置ofeasable代码是太大的平均失真的代码被检查individual.In这个项目中，我们研究了一种新的技术，称为扰动理论，减少theset可行的代码到一个更小的代码集称为扰动码。在许多情况下，最佳码是扰动码之一，并且可以在合理的时间内找到。可行码集合中的每个线性卷积码都通过二进制域上的奇偶校验矩阵来描述，该二进制域由固定数量的行和列组成。扰动类码由奇偶校验矩阵可以排列成顶部一定数量的行保持固定的码组成。根据校验矩阵的哪一行是固定的，任何码都属于不止一个扰动类码，在一定条件下，扰动类码的校验矩阵上会有一个自然群起作用.利用群结构，每个扰动类的代码的一个子集被选择。如果一个代码是包含该代码的一定数量的扰动类中的选定代码，则该代码将被声明为扰动代码。在扰动码的定义上存在着一些不确定性。在这个项目中，我们研究了如何正确地描述扰动码的概念，以便可以从一个小的扰动码集中找到一个最佳的代码，源和信道模型的充分对称性。

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.