Some Results on Update Complexity of a Linear Code Ensemble
Alan Jule, Iryna Andriyanova · 2011
In this paper, the update complexity of a linear code ensemble (binary or nonbinary) is considered. The update complexity has been proposed in 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 γmaxand the average update complexity γavgof a code ensemble are distinguished in this paper. In the first part of the paper, we propose a simple lower bound on the γavgand further evaluate its general expression. In the second part, we show how a simple upper bound on γavgfor 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.