Some Results on Update Complexity of a Linear Code Ensemble
In this paper, the update complexity of a linear code ensemble (binary or nonbinary) is considered. The update complexity has been proposed in 1 as a measure of the number of updates needed to be done within the bits of a codeword, if one of information bits, encoded in this codeword, has been changed. The update efficiency is a performance measure of distributed storage applications, that naturally use erasure-correction coding. The maximum update complexity γmax and the average update complexity γavg of a code ensemble are distinguished in this paper. In the first part of the paper, we propose a simple lower bound on the γavg and further evaluate its general expression. In the second part, we show how a simple upper bound on γavg for sparse graph codes can be obtained, on a particular example of binary LDPC codes. One of interesting results of the paper is that code ensembles with polynomial minimum distance growth have the update complexity which grows linearly in the codelength, i.e. they are not update-efficient.
Alan Jule Iryna Andriyanova
R&D group Axalot 92800 Puteaux, France ETIS group ENSEA/UCP/CNRS-UMR8051 95014 Cergy-Pontoise, Franc ETIS group ENSEA/UCP/CNRS-UMR8051 95014 Cergy-Pontoise, France
国际会议
2011 International Symposium on Network Coding(2011网络编码国际会议 NETCOD 2011)
北京
英文
1-5
2011-07-25（万方平台首次上网日期，不代表论文的发表时间）