  The encoding complexity of a general (en,ek) quasi-cyclic code is
O[(e^2)(n-k)k]. This paper presents a novel low-complexity encoding algorithm
for quasi-cyclic (QC) codes based on matrix transformation. First, a message
vector is encoded into a transformed codeword in the transform domain. Then,
the transmitted codeword is obtained from the transformed codeword by the
inverse Galois Fourier transform. For binary QC codes, a simple and fast
mapping is required to post-process the transformed codeword such that the
transmitted codeword is binary as well. The complexity of our proposed encoding
algorithm is O[e(n-k)k] symbol operations for non-binary codes and
O[ek(n-k)(log_2 e)] bit operations for binary codes. These complexities are
much lower than their traditional counterpart O[(e^2)(n-k)k]. For example, our
complexity of encoding a 64-ary (4095,2160) QC code is only 1.59% of that of
traditional encoding, and our complexities of encoding the binary (4095, 2160)
and (8176, 7154) QC codes are respectively 9.52% and 1.77% of those of
traditional encoding. We also study the application of our low-complexity
encoding algorithm to one of the most important subclasses of QC codes, namely
QC-LDPC codes, especially when their parity-check matrices are rank deficient.
