... Complexity¹

A version of this paper appeared in the IEEE Transactions on Information Theory, Volume 48, Number 1, Jan. 2002, pp. 89.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...1²

A version of this paper appeared at the 31st Annual Conference on Information Sciences and Systems.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Trachtenberg³

The author is with the Department of Electrical and Computer Engineering, Boston University, Boston, MA 02215 (e-mail: trachten@bu.edu).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...3⁴

This work was supported by the Computational Science and Engineering Program at the University of Illinois at Urbana/Champaign.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... non-trivial⁵

A non-trivial code is one whose generator matrix contains no all-zero columns.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... code.⁶

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.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.