... Complexity1
A version of this paper appeared in the IEEE Transactions on Information Theory, Volume 48, Number 1, Jan. 2002, pp. 89.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...12
A version of this paper appeared at the 31st Annual Conference on Information Sciences and Systems.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... Trachtenberg3
The author is with the Department of Electrical and Computer Engineering, Boston University, Boston, MA 02215 (e-mail: trachten@bu.edu).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...34
This work was supported by the Computational Science and Engineering Program at the University of Illinois at Urbana/Champaign.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... non-trivial5
A non-trivial code is one whose generator matrix contains no all-zero columns.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... code.6
We do have to take some care that when we delete the generator the resulting code is non-trivial. If the generator matrix of the resulting code has an all-zero column, making the code trivial, we may simply delete the offending column.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.