Constructing Linear Codes with Good Spectra
Shengtian~Yang
~\IEEEmembership{Member,~IEEE,} Thomas~Honold
~\IEEEmembership{Member,~IEEE,} Yan~Chen
~\IEEEmembership{Member,~IEEE,} Zhaoyang~Zhang
~\IEEEmembership{Member,~IEEE,} Peiliang~Qiu
Linear codes with good joint spectra are good candidates for lossless joint source-channel coding (JSCC). However, in spite of their existence, it is still unknown how to construct them in practice. This paper is devoted to the construction of such codes. In particular, two families of linear codes are presented and proved to have good joint spectra. The first family is derived from Gabidulin codes, a class of maximum-rank-distance (MRD) codes. The second is constructed by a serial concatenation of an inner low-density generator matrix (LDGM) code and an outer low-density parity-check (LDPC) code. The general criteria of good linear codes are also reviewed and discussed for three cases: lossless source coding, channel coding, and lossless JSCC, respectively. In the framework of code-spectrum approach, it is shown that all these issues just correspond to the problems of constructing linear codes with good kernel spectra, good image spectra, and good joint spectra, respectively. Furthermore, it is shown that good joint spectra imply good kernel spectra and good image spectra. This fact thus establishes the fundamental role of linear codes with good joint spectra. Conversely, it is proved that, when the output (resp., input) alphabet is an elementary abelian group, there exist linear codes with not only good joint spectra but also the same kernel (resp., image) of any given linear code that has a good kernel (resp., image) spectrum.
JSCC3.tex
%% 2008/07/01
%% Cerated by Shengtian Yang
%% yangshengtian@zju.edu.cn
%%
%% NOTE: This text file uses MS Windows line feed conventions. When (human)
%% reading this file on other platforms, you may have to use a text
%% editor that can handle lines terminated by the MS Windows line feed
%% characters (0x0D 0x0A).
%%
%% This paper requires IEEEtran.cls version 1.7a or later.
%%

\documentclass[peerreview]{IEEEtran}%,journal

% some very useful LaTeX packages include:
\usepackage[noadjust]{cite}

\usepackage{graphicx}

\usepackage[cmex10]{amsmath}
\interdisplaylinepenalty=2500

\usepackage{amsopn}
\usepackage{amssymb}
\usepackage{bm}
\usepackage{cases}

%\usepackage[dvipdfmx,pdfstartview=FitH]{hyperref}


\def\baselinestretch{1.45}

% some macro definitions

% for reference
%\newcommand{\eqref}[1]{\textnormal{(\ref{#1})}}

% for mathematical expression
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\renewcommand{\IEEEQED}{\IEEEQEDopen}
\newenvironment{proofof}[2][Proof of]{\begin{IEEEproof}[#1 {#2}]}{\end{IEEEproof}}

% for relation operators
\newcommand{\relvar}[2]{\buildrel {#2} \over {#1}}
\newcommand{\eqvar}[1]{\relvar{=}{\mathrm{#1}}}
\newcommand{\ltvar}[1]{\relvar{<}{\mathrm{#1}}}
\newcommand{\gtvar}[1]{\relvar{>}{\mathrm{#1}}}
\newcommand{\levar}[1]{\relvar{\le}{\mathrm{#1}}}
\newcommand{\gevar}[1]{\relvar{\ge}{\mathrm{#1}}}
\newcommand{\eqdef}{\eqvar{\scriptscriptstyle\triangle}}

% for multiple-line expressions
\newcommand{\findent}{\hspace{1em}}
\newlength{\nullrellength}
\settowidth{\nullrellength}{=}
\newcommand{\nullrel}{\:\hspace{\nullrellength}\:}
\newcommand{\breakop}[1]{\hspace{-0.2222em}{}#1}

% for limit operation
\DeclareMathOperator*{\plimsup}{p-lim\,sup}
\DeclareMathOperator*{\pliminf}{p-lim\,inf}
\DeclareMathOperator*{\plim}{p-lim}

% for special sets
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\pintegers}{\mathbb{N}}
\newcommand{\nnintegers}{\mathbb{N}_0}
\newcommand{\realnumbers}{\mathbb{R}}
\newcommand{\complexnumbers}{\mathbb{C}}
\newcommand{\unitsof}[1]{{#1^{\times}}}
\newcommand{\nonzerocomplexnumbers}{\unitsof{\complexnumbers}}
\newcommand{\field}[1]{\mathbb{F}_{#1}}
\newcommand{\fieldstar}[1]{\unitsof{\field{#1}}}
\newcommand{\binaryset}{\mathbb{B}}
\newcommand{\symmetricgroup}[1]{\mathrm{S}_{#1}}
\newcommand{\seqspace}[1]{{#1}^{*}}

% for weight
\newcommand{\wtlogo}{\mathrm{w}}
\newcommand{\weight}[1]{W_{#1}}

% for vector and matrix
\newcommand{\seq}[1]{\mathbf{#1}}
\newcommand{\seqx}[1]{\bm{#1}}
\newcommand{\mat}[1]{\mathbf{#1}}
\newcommand{\matentry}[1]{\mathrm{#1}}
\newcommand{\transpose}[1]{{#1}^{T}}
\newcommand{\rank}[1]{\mathrm{rank}{\left({#1}\right)}}
\newcommand{\rdist}{\mathrm{d}_{\mathrm{R}}}%rank distance

% asymptotic notations
\DeclareMathOperator{\order}{\Theta}
\DeclareMathOperator{\uorder}{O}
\DeclareMathOperator{\lorder}{\Omega}

% for special functions
\newcommand{\floor}[1]{\left\lfloor {#1} \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil {#1} \right\rceil}

% for special operators
\newcommand{\pprod}{\odot}
\newcommand{\bigpprod}{\bigodot}
\newcommand{\rtilde}[1]{#1^{\sim}}
\newcommand{\ltilde}[1]{{}^{\sim}\!#1}
\newcommand{\coef}[1]{\mathrm{coef}{\left({#1}\right)}}

% for special codes
\newcommand{\codevar}[2]{f^{\mathrm{#1}}_{#2}}
\newcommand{\rcodevar}[2]{F^{\mathrm{#1}}_{#2}}
\newcommand{\rcodetildevar}[2]{\tilde{F}^{\mathrm{#1}}_{#2}}
\newcommand{\rlccode}[1]{\rcodevar{RLC}{#1}}
\newcommand{\rlccodetilde}[1]{\rcodetildevar{RLC}{#1}}
\newcommand{\rmcode}[1]{\rcodevar{RM}{#1}}
\newcommand{\sgcode}[1]{\rcodevar{SG}{#1}}
\newcommand{\ldcode}[1]{\rcodevar{LD}{#1}}
\newcommand{\repcode}[1]{\codevar{REP}{#1}}
\newcommand{\rrepcode}[1]{\rcodevar{REP}{#1}}
\newcommand{\chkcode}[1]{\codevar{CHK}{#1}}
\newcommand{\rchkcode}[1]{\rcodevar{CHK}{#1}}


\begin{document}

\title{Constructing Linear Codes with Good Spectra}
\author{Shengtian~Yang,~\IEEEmembership{Member,~IEEE,} Thomas~Honold,~\IEEEmembership{Member,~IEEE,} Yan~Chen,~\IEEEmembership{Member,~IEEE,} Zhaoyang~Zhang,~\IEEEmembership{Member,~IEEE,} Peiliang~Qiu,~\IEEEmembership{Member,~IEEE}
\thanks{The material in this paper was presented in part at the 2008 International Conference on Communications and Networking in China (CHINACOM'08), Hangzhou, China, August 2008.}
\thanks{This work was supported in part by the Natural Science Foundation of China under Grants 60772093, 60802014, and 60872063, the Chinese Specialized Research Fund for the Doctoral Program of Higher Education under Grants 200803351023 and 200803351027, the National High Technology Research and Development Program of China under Grant 2007AA01Z257, and the Zhejiang Provincial Natural Science Foundation of China under Grant Y106068.}
\thanks{S. Yang was with the Department of Information Science and Electronic Engineering, Zhejiang University, Hangzhou 310027, China and also with Zhejiang Provincial Key Laboratory of Information Network Technology, Zhejiang University, Hangzhou 310027, China. He is now self-employed at Zhengyuan Xiaoqu 10-2-101, Hangzhou 310011, China (email: yangst@codlab.net).}
\thanks{T. Honold is with the Department of Information Science and Electronic Engineering, Zhejiang University, Hangzhou 310027, China (email: honold@zju.edu.cn).}
\thanks{Y. Chen was with the Department of Information Science and Electronic Engineering, Zhejiang University, Hangzhou 310027, China. She is now with Huawei Technologies Co., Ltd (Shanghai), Shanghai 201206, China (email: eeyanchen@huawei.com).}
\thanks{Z. Zhang and P. Qiu are with the Department of Information Science and Electronic Engineering, Zhejiang University, Hangzhou 310027, China (email: ning\_ming@zju.edu.cn; qiupl@zju.edu.cn).}
}

% The paper headers
\markboth{Revised for the Second Round Review of IEEE Transactions on Information Theory (Version: \today)}{}

% If you want to put a publisher's ID mark on the page
% (can leave text blank if you just want to see how the
% text height on the first page will be reduced by IEEE)
%\pubid{0000--0000/00\$00.00~\copyright~2002 IEEE}

\maketitle

\begin{abstract}
Linear codes with good joint spectra are good candidates for lossless joint source-channel coding (JSCC). However, in spite of their existence, it is still unknown how to construct them in practice. This paper is devoted to the construction of such codes. In particular, two families of linear codes are presented and proved to have good joint spectra. The first family is derived from Gabidulin codes, a class of maximum-rank-distance (MRD) codes. The second is constructed by a serial concatenation of an inner low-density generator matrix (LDGM) code and an outer low-density parity-check (LDPC) code. The general criteria of good linear codes are also reviewed and discussed for three cases: lossless source coding, channel coding, and lossless JSCC, respectively. In the framework of code-spectrum approach, it is shown that all these issues just correspond to the problems of constructing linear codes with good kernel spectra, good image spectra, and good joint spectra, respectively. Furthermore, it is shown that good joint spectra imply good kernel spectra and good image spectra. This fact thus establishes the fundamental role of linear codes with good joint spectra. Conversely, it is proved that, when the output (resp., input) alphabet is an elementary abelian group, there exist linear codes with not only good joint spectra but also the same kernel (resp., image) of any given linear code that has a good kernel (resp., image) spectrum.
\end{abstract}

\begin{keywords}
Code spectra, Gabidulin codes, linear codes, low-density generator matrix (LDGM) codes, low-density parity-check (LDPC) codes, MacWilliams identities, maximum-rank-distance (MRD) codes.
\end{keywords}

\IEEEpeerreviewmaketitle

\section{Introduction}

Linear codes, owing to their good structure, are widely applied in the areas of channel coding, source coding, and joint source-channel coding (JSCC). Undoubtedly, constructing good linear codes is always one of the most important and everlasting topics in these areas. As we know, a variety of good linear codes such as Turbo codes \cite{JSCC:Berrou199305} and low-density parity-check (LDPC) codes \cite{JSCC:Gallager196300, JSCC:MacKay199903} have been constructed for channel coding. And in the past decade, the parity-check matrices of good linear codes for channel coding have been employed as encoders for distributed source coding. They proved good in both theory \cite{JSCC:Muramatsu200510, JSCC:Yang200503} and practice \cite{JSCC:Pradhan200100, JSCC:Stankovic200604, JSCC:Coleman200608}. However, in the general cases of lossless JSCC (based on linear codes), it is still unknown what kinds of linear codes are good and how to construct them. We do not even know how to design an implementable optimal JSCC scheme based on linear codes for arbitrary sources and channels. For instance, much work on practical designs of lossless JSCC based on linear codes has been done for transmission of specific correlated sources over specific multiple-access channels (MACs), e.g., correlated sources over separated noisy channels \cite{JSCC:Garcia200103, JSCC:Zhong200505, JSCC:Zhao200611a}, correlated sources over additive white Gaussian noise (AWGN) MACs \cite{JSCC:Murugan200408,JSCC:Garcia200709}, and correlated sources over Rayleigh fading MACs \cite{JSCC:Zhao200611b}, but it is still not clear how to construct an implementable optimal lossless JSCC scheme for a general case. The same problem also exists in the case of point-to-point transmission, but since traditional (nonlinear) source coding techniques combined with joint source-channel decoding work well in this case, linear-code-based schemes are not so important as in distributed JSCC. One exception is when we need a simple universal encoder, that is, the encoder does not require any knowledge of the source statistics. For background information of lossless JSCC in the point-to-point case, we refer to \cite{JSCC:Zhu200408,JSCC:Jaspar200706} and the references therein.

Recently, for lossless transmission of correlated sources over MACs, we proposed a general scheme based on linear codes \cite{JSCC:Yang200904}, which was proved to be optimal if good linear codes and good conditional probabilities are chosen. Fig.~\ref{fig:Scheme1} illustrates the mechanism of the encoding scheme (see \cite[Sec.~III-C]{JSCC:Yang200904}), which can also be formulated as
$$
\Phi_n(\seq{v}) \eqdef q_n(\seq{v}, \Sigma_l(F_n(\Sigma_n(\seq{v}))) + \bar{U}^l) \qquad \forall \seq{v} \in \mathcal{V}^n.
$$
Roughly speaking, the scheme consists of two steps. First, the source sequence $\seq{v}$ is processed by a random affine mapping, i.e, $(\Sigma_l \circ F_n \circ \Sigma_n)(\seq{v}) + \bar{U}^l$, where $F_n$ is a random linear code, $\Sigma_l$ and $\Sigma_n$ are independent uniform random interleavers, and $\bar{U}^l$ is an independent uniform random vector. Secondly, the output of the first step, together with the source sequence, is fed into the quantization mapping $q_n$ to yield the final output. The first step is to generate uniformly distributed output with the so-called pairwise-independence property, while the second step is to shape the output so that it is suitable for a given channel. Accordingly, two main issues arise: how do we design a good linear code $F_n$ and a good quantization mapping $q_n$ which fulfill the above two goals, respectively? About the former, we proved in \cite{JSCC:Yang200904} that linear codes with good joint spectra (a generalization of input-output weight distributions) are good candidates. Hence, to design a lossless JSCC scheme in practice, a big problem is how to construct linear codes with good joint spectra. To our knowledge, however, this problem has never been studied before.
\begin{figure*}[htbp]
\centering
\includegraphics{JSCCFig1}
\caption{The proposed lossless joint source-channel encoding scheme based on linear codes for multiple-access channels in \cite{JSCC:Yang200904}}
\label{fig:Scheme1}
\end{figure*}

In this paper, we shall give a thorough investigation of this problem. Our main tool is the code-spectrum approach \cite{JSCC:Yang200904}. As we shall see, the spectra of a linear code, including kernel spectrum, image spectrum, and especially joint spectrum, provide important characterization on its performance for most applications. The rest of this paper is organized as follows.

In Section~\ref{sec:NotationsAndConventions}, we introduce the basic notations and conventions used throughout the paper. In Section~\ref{sec:BasicsOfCodeSpectrumApproach}, we briefly review the code-spectrum approach. Then in Section~\ref{sec:NewMethodsAndResultsOfCodeSpectrum}, we develop some new notions and methods to facilitate the calculation of spectra, including properties of vector permutations (Section~\ref{subsec:NewResultsI}), a viewpoint of regarding coding modules as conditional probability distributions (Section~\ref{subsec:NewResultsII}), spectrum generating functions and spectra with coordinate partitions (Sections~\ref{subsec:NewResultsIIIpre} and \ref{subsec:NewResultsIII}), and the MacWilliams identities (Section~\ref{subsec:NewResultsV}).

In Section~\ref{sec:ConceptsOfGoodLinearCodes}, we review the original requirements of good linear codes for lossless source coding, channel coding, and lossless JSCC, respectively. To each original requirement there just corresponds a spectrum criterion of linear codes, which is the kernel-spectrum condition, the image-spectrum condition, and the joint-spectrum condition, respectively. Then with each criterion there is associated a family of linear codes. They are called \emph{$\delta$-asymptotically good linear source codes} (LSCs), \emph{$\delta$-asymptotically good linear channel codes} (LCCs), and \emph{$\delta$-asymptotically good linear source-channel codes} (LSCCs), respectively. We show that, under some conditions, good LSCCs are also good in the sense of LSCs and LCCs. Thus the problem of constructing good LSCCs (i.e., linear codes with good joint spectra) is of particular interest and importance.

Based on this observation, in Section~\ref{sec:GeneralPrinciplesForConstructingGoodLSCC}, we proceed to study the general principles for constructing good LSCCs. In Section~\ref{subsec:MRDLSCC}, we provide a family of good LSCCs which are derived from so-called maximum-rank-distance (MRD) codes. In Section~\ref{subsec:ConstructingGoodLSCCGPA}, we investigate the problem of how to construct a good LSCC with the same kernel (resp., image) of a given good LSC (resp., LCC). In Section~\ref{subsec:ConstructingGoodLSCCGPB}, we propose a general serial concatenation scheme for constructing good LSCCs.

In light of this general scheme, in Section~\ref{sec:ExplicitConstruction}, we turn to the analysis of joint spectra of regular low-density generator matrix (LDGM) codes. We show that the joint spectra of regular LDGM codes with appropriate parameters are approximately $\delta$-asymptotically good. Based on this fact, we finally present a family of good LSCCs by a serial concatenation of an inner LDGM code and an outer LDPC code.

All the proofs are presented in Section~\ref{sec:Proofs}, and Section~\ref{sec:Conclusion} concludes the paper.


\section{Notations and Conventions}\label{sec:NotationsAndConventions}

In this section, we introduce some basic notations and conventions used throughout the paper.

\begin{itemize}

\item In general, symbols, real variables, and deterministic mappings are denoted by lowercase letters. Sets, matrices, and random elements are denoted by capital letters. Alphabets are denoted by script capital letters.

\item The symbol $\varnothing$ denotes the empty set.

\item The cardinality of a set $A$ is denoted by $|A|$.

\item The symbols $\integers$, $\pintegers$, $\nnintegers$, $\realnumbers$, $\complexnumbers$ denote the ring of integers, the set of positive integers, the set of nonnegative integers, the field of real numbers, and the field of complex numbers, respectively. For a prime power $q>1$ the finite field of order $q$ is denoted by $\field{q}$. The multiplicative subgroup of nonzero elements of $\field{q}$ is denoted by $\fieldstar{q}$ (and similarly for other fields).

\item For any $n \in \pintegers$, we define the index set $\mathcal{I}_n \eqdef \{1, \ldots, n\}$.

\item The symbol $\mathcal{X}^n$ denotes the $n$-fold Cartesian product of the alphabet $\mathcal{X}$. A sequence (or vector) in $\mathcal{X}^n$ is denoted by $\seq{x} = x_1 x_2 \cdots x_n$, where $x_i$ denotes the $i$th component of $\seq{x}$. For any set $A = \{a_1, a_2, \dots, a_r\} \subseteq \mathcal{I}_n$ with $a_1 < a_2 < \dots < a_r$, we define the sequence $(x_i)_{i \in A}$ or $x_A$ as $x_{a_1}x_{a_2}\cdots x_{a_r}$. Clearly, one may write $x_{\mathcal{I}_n}$ in place of $\seq{x}$. We use the notation $a^l$ for the $l$ times repetition of a single symbol $a \in \mathcal{X}$, or simply write $\seqx{a}$ to represent an all-$a$ sequence without explicitly indicating the length.

\item The length of a sequence $\seq{x}$ is denoted by $|\seq{x}|$. 

\item By default, any vectors are regarded as row vectors. An $m \times n$ matrix is denoted by $\mat{M} = (\matentry{M}_{i,j})_{i \in \mathcal{I}_m, j \in \mathcal{I}_n}$, where $\matentry{M}_{i,j}$ denotes the $(i,j)$-th entry. The transpose of a matrix $\mat{M}$ is denoted by $\transpose{\mat{M}}$. The set of all $m \times n$-matrices over a field (ring) $F$ is denoted by $F^{m \times n}$. The set $F^{m \times n}$ forms a vector space (resp., module) over $F$ and in the square case $m=n$ an $F$-algebra relative to the vector space (resp., module) operations and matrix multiplication.

\item For any functions $f: \mathcal{X} \to \mathcal{Y}$ and $g: \mathcal{Y} \to \mathcal{Z}$, we define the composite $g \circ f: \mathcal{X} \to \mathcal{Z}$ by $(g\circ f)(x)\eqdef g(f(x))$.

\item For any functions $f: \mathcal{X}_1 \to \mathcal{Y}_1$ and $g: \mathcal{X}_2 \to \mathcal{Y}_2$, we define the Cartesian product $f \pprod g: \mathcal{X}_1 \times \mathcal{X}_2 \to \mathcal{Y}_1 \times \mathcal{Y}_2$ by $(f \pprod g)(x_1, x_2) \eqdef (f(x_1), g(x_2))$.

\item The function $1\{\cdot\}$ is a mapping defined by $1\{\mathrm{true}\} = 1$ and $1\{\mathrm{false}\} = 0$. Then, the indicator function of a subset $A$ of a set $X$ can be written as $1\{x \in A\}$.

\item A permutation on $n$ letters is a one-to-one mapping of $\mathcal{I}_n$ onto $\mathcal{I}_n$. The group of all permutations on $n$ letters is denoted by $\symmetricgroup{n}$.

\item For a finite set $A$, the ring of polynomials in the indeterminates $X_a$, $a \in A$, and with coefficients in $\complexnumbers$ is denoted by $\complexnumbers[X_a; a \in A]$. The ring $\complexnumbers[X_a; a \in A]$ can be defined as a subring (consisting of all elements of finite support) of the semigroup algebra of $\nnintegers^A$ (the additive semigroup of all mappings $A \to \nnintegers$) over $\complexnumbers$. For readers not familiar with this concept we remark that for any ordering $A = \{a_1, a_2, \dots, a_n\}$, $n = |A|$, of the elements of $A$ we obtain an isomorphism $\complexnumbers[X_1, X_2, \dots, X_n] \to \complexnumbers[X_a; a \in A]$ by setting $X_i \mapsto X_{a_i}$.

\item When performing probabilistic analysis, all objects of study are related to a basic probability space $(\Omega, \mathcal{A}, P)$ where $\mathcal{A}$ is a $\sigma$-algebra (or $\sigma$-field) in $\Omega$ and $P$ is a probability measure on $(\Omega, \mathcal{A})$. For any event $A \in \mathcal{A}$, $PA = P(A)$ is called the probability of $A$. Any measurable mapping of $\Omega$ into some measurable space $(B, \mathcal{B})$ is generally called a random element.

\item For any random elements $F$ and $G$ in a common measurable space, the equality $F \eqvar{d} G$ means that $F$ and $G$ have the same probability distribution.

\item For any sequence $\{Z_n\}_{n=1}^\infty$ of real-valued random variables, we introduce two probabilistic limit operations, i.e., the \emph{limit superior in probability} $\plimsup_{n \to \infty} Z_n$ defined by
$$
\plimsup_{n \to \infty} Z_n \eqdef \inf\left\{ \alpha \left| \lim_{n \to \infty} P\{Z_n > \alpha\} = 0 \right.\right\}
$$
and the \emph{limit inferior in probability} $\pliminf_{n \to \infty} Z_n$ defined by
$$
\pliminf_{n \to \infty} Z_n \eqdef \sup\left\{ \beta \left| \lim_{n \to \infty} P\{Z_n < \beta\} = 0 \right.\right\}.
$$
As
$$
\plimsup_{n \to \infty} Z_n = \pliminf_{n \to \infty} Z_n = c
$$
we say that the \emph{limit in probability} of $\{Z_n\}_{n=1}^\infty$ is
$$
\plim_{n \to \infty} Z_n = c.
$$

\item For any random sets or functions, we tacitly assume that their $n$-fold Cartesian products (e.g., $A^n$ or $\bigpprod_{i=1}^n F$) are Cartesian products of their independent copies.

\item All logarithms are taken to the natural base $\mathrm{e}$ and denoted by $\ln$.

\item For any probability distribution $P$ on some alphabet $\mathcal{X}$, the \emph{entropy} $H(P)$ is defined by
$$
H(P) \eqdef \sum_{a \in \mathcal{X}} P(a) \ln \frac{1}{P(a)}.
$$
For any probability distributions $P$ and $Q$ on some alphabet $\mathcal{X}$, the \emph{information divergence} $D(P\|Q)$ is defined by
$$
D(P\|Q) \eqdef \sum_{a \in \mathcal{X}} P(a) \ln \frac{P(a)}{Q(a)}.
$$
For any number $x, y \in [0, 1]$, the \emph{information divergence function} $D(x\|y)$ is defined by
$$
D(x\|y) \eqdef D((x,1-x)\|(y,1-y)).
$$

\item For $x\in\realnumbers$, $\ceil{x}$ denotes the smallest integer not exceeded by $x$.

\item For any real functions $f(n)$ and $g(n)$ with $n \in \pintegers$, the asymptotic $\Theta$-notation $f(n)=\order(g(n))$ means that there exist positive constants $c_1$ and $c_2$ such that
\[
c_1g(n) \le f(n) \le c_2g(n).
\]
for sufficiently large $n$.
\end{itemize}


\section{Basics of the Code-Spectrum Approach}\label{sec:BasicsOfCodeSpectrumApproach}

In this section, we briefly introduce the basics of the code-spectrum approach \cite{JSCC:Yang200904}, which is a generalization of the weight-distribution approach, e.g., \cite{JSCC:Divsalar199809, JSCC:Wood199903}.

Let $\mathcal{X}$ and $\mathcal{Y}$ be two finite (additive) abelian groups. We define a \emph{linear code} as a homomorphism $f: \mathcal{X}^n \to \mathcal{Y}^m$. The (coding) rate $R(f)$ of $f$ is defined to be the ratio $n / m$.

Note that, by defining
$$
\sigma(\seq{x}) \eqdef x_{\sigma^{-1}(1)} x_{\sigma^{-1}(2)} \cdots x_{\sigma^{-1}(n)} \qquad \forall \seq{x} \in \mathcal{X}^n
$$
any permutation $\sigma\in\symmetricgroup{n}$ induces an automorphism of $\mathcal{X}^n$. For each $n \in \pintegers$, we denote by $\Sigma_n$ a uniformly distributed random permutation on $n$ letters, that is,
$$
P\{\Sigma_n = \sigma\} = \frac{1}{n!} \qquad \forall \sigma \in \symmetricgroup{n}.
$$
We tacitly assume that different random permutations occurring in the same expression are independent, and the notations such as $\Sigma_m$ and $\Sigma_n$ represent different random permutations though it is possible that $m = n$.

Next, we introduce the concept of types \cite{JSCC:Csiszar198100}. The \emph{type} of a sequence $\seq{x}$ in $\mathcal{X}^n$ is the empirical distribution $P_{\seq{x}}$ on $\mathcal{X}$ defined by
$$
P_{\seq{x}}(a) \eqdef \frac{1}{|\seq{x}|} \sum_{i=1}^{|\seq{x}|} 1\{x_i = a\} \qquad \forall a \in \mathcal{X}.
$$
For a (probability) distribution $P$ on $\mathcal{X}$, the set of sequences of type $P$ in $\mathcal{X}^n$ is denoted by $\mathcal{T}_P^n(\mathcal{X})$. A distribution $P$ on $\mathcal{X}$ is called a type of sequences in $\mathcal{X}^n$ if $\mathcal{T}_P^n(\mathcal{X}) \ne \varnothing$. We denote by $\mathcal{P}(\mathcal{X})$ the set of all distributions on $\mathcal{X}$, and denote by $\mathcal{P}_n(\mathcal{X})$ the set of all types of sequences in $\mathcal{X}^n$.

Now we introduce the concept of spectra. The \emph{spectrum} of a nonempty set $A \subseteq \mathcal{X}^n$ is the empirical distribution $S_{\mathcal{X}}(A)$ on $\mathcal{P}_n(\mathcal{X})$ defined by
$$
S_{\mathcal{X}}(A)(P) \eqdef \frac{|\{\seq{x} \in A | P_{\seq{x}} = P\}|}{|A|} \qquad \forall P \in \mathcal{P}_n(\mathcal{X}).
$$
The spectrum of $A\subseteq \mathcal{X}^n$ is closely related to the \emph{complete weight distribution} of $A$ (see for example, \cite[Ch.~7.7]{JSCC:Huffman200300} or \cite[Sec.~10]{JSCC:Pless199800}), which can be defined as follows: For $\seq{x}\in\mathcal{X}^n$ and $a\in\mathcal{X}$ let $N_{\seq{x}}(a)=|\{i \in \mathcal{I}_n | x_i=a\}|=nP_{\seq{x}}(a)$. This defines a function $N_{\seq{x}}: \mathcal{X} \to \nnintegers$ with $\sum_{a\in\mathcal{X}} N_{\seq{x}}(a) = n$. The complete weight distribution of $A$ is then defined as the function $\nnintegers^{\mathcal{X}} \to \nnintegers$, $N \mapsto |\{\seq{x} \in A | N_{\seq{x}} = N\}|=|A|\cdot S_{\mathcal{X}}(A)(N/n)$. (For the last equality we need to assume that $N/n\in\mathcal{P}_n(\mathcal{X})$, i.e. $\sum_{a\in\mathcal{X}}N(a)=n$, but this is only a technical issue.) Spectrum and complete weight distribution thus differ only by scaling factors in both domain and range.

Analogously, the \emph{joint spectrum} of a nonempty set $B \subseteq \mathcal{X}^n \times \mathcal{Y}^m$ is the empirical distribution $S_{\mathcal{X}\mathcal{Y}}(B)$ on $\mathcal{P}_n(\mathcal{X}) \times \mathcal{P}_m(\mathcal{Y})$ defined by
\begin{IEEEeqnarray*}{l}
S_{\mathcal{X}\mathcal{Y}}(B)(P, Q) \eqdef \frac{|\{(\seq{x}, \seq{y}) \in B | P_{\seq{x}} = P, P_{\seq{y}} = Q\}|}{|B|} \\
\hspace{12em} \forall P \in \mathcal{P}_n(\mathcal{X}), Q \in \mathcal{P}_m(\mathcal{Y}).
\end{IEEEeqnarray*}
By considering the marginal and conditional distributions of $S_{\mathcal{X}\mathcal{Y}}(B)$, we obtain the \emph{marginal spectra} $S_{\mathcal{X}}(B)$, $S_{\mathcal{Y}}(B)$ and the \emph{conditional spectra} $S_{\mathcal{Y}|\mathcal{X}}(B)$, $S_{\mathcal{X}|\mathcal{Y}}(B)$, that is,
$$
S_{\mathcal{X}}(B)(P) \eqdef \sum_{Q \in \mathcal{P}_m(\mathcal{Y})} S_{\mathcal{X}\mathcal{Y}}(B)(P, Q)
$$
$$
S_{\mathcal{Y}}(B)(Q) \eqdef \sum_{P \in \mathcal{P}_n(\mathcal{X})} S_{\mathcal{X}\mathcal{Y}}(B)(P, Q).
$$
\begin{IEEEeqnarray*}{l}
S_{\mathcal{Y}|\mathcal{X}}(B)(Q|P) \eqdef \frac{S_{\mathcal{X}\mathcal{Y}}(B)(P, Q)}{S_{\mathcal{X}}(B)(P)} \\
\hspace{10em} \forall P \mbox{ satisfying } S_{\mathcal{X}}(B)(P) \ne 0
\end{IEEEeqnarray*}
\begin{IEEEeqnarray*}{l}
S_{\mathcal{X}|\mathcal{Y}}(B)(P|Q) \eqdef \frac{S_{\mathcal{X}\mathcal{Y}}(B)(P, Q)}{S_{\mathcal{Y}}(B)(Q)} \\
\hspace{10em} \forall Q \mbox{ satisfying } S_{\mathcal{Y}}(B)(Q) \ne 0.
\end{IEEEeqnarray*}

Furthermore, for any given function $f: \mathcal{X}^n \to \mathcal{Y}^m$, we can define its \emph{joint spectrum} $S_{\mathcal{X}\mathcal{Y}}(f)$, \emph{forward conditional spectrum} $S_{\mathcal{Y}|\mathcal{X}}(f)$, \emph{backward conditional spectrum} $S_{\mathcal{X}|\mathcal{Y}}(f)$, and \emph{image spectrum} $S_{\mathcal{Y}}(f)$ as $S_{\mathcal{X}\mathcal{Y}}(\mathrm{rl}(f))$, $S_{\mathcal{Y}|\mathcal{X}}(\mathrm{rl}(f))$, $S_{\mathcal{X}|\mathcal{Y}}(\mathrm{rl}(f))$, and $S_{\mathcal{Y}}(\mathrm{rl}(f))$, respectively, where $\mathrm{rl}(f)$ is the relation defined by $\{(\seq{x}, f(\seq{x})) | \seq{x} \in \mathcal{X}^n\}$. In this case, the forward conditional spectrum is given by
$$
S_{\mathcal{Y}|\mathcal{X}}(f)(Q|P) = \frac{S_{\mathcal{X}\mathcal{Y}}(f)(P, Q)}{S_{\mathcal{X}}(\mathcal{X}^n)(P)}.
$$
If $f$ is a linear code, we further define its \emph{kernel spectrum} as $S_{\mathcal{X}}(\ker f)$, where $\ker f \eqdef \{\seq{x} \in \mathcal{X}^n | f(\seq{x}) = 0^m\}$. In this case, we also have $S_{\mathcal{Y}}(f) = S_{\mathcal{Y}}(f(\mathcal{X}^n))$ since $f$ is a homomorphism of groups.

The above definitions can be easily extended to more general cases. For example, we may consider the joint spectrum $S_{\mathcal{X}\mathcal{Y}\mathcal{Z}}(C)$ of a set $C \subseteq \mathcal{X}^n \times \mathcal{Y}^m \times \mathcal{Z}^l$, or consider the joint spectrum $S_{\mathcal{X}_1\mathcal{X}_2\mathcal{Y}_1\mathcal{Y}_2}(g)$ of a function $g: \mathcal{X}_1^{n_1} \times \mathcal{X}_2^{n_2} \to \mathcal{Y}_1^{m_1} \times \mathcal{Y}_2^{m_2}$.

A series of properties about the spectra of codes were given in \cite[Sec.~II]{JSCC:Yang200904}. We list below some results for easy reference.

\begin{proposition}\label{pr:SpectrumOfSets}
For all $P \in \mathcal{P}_n(\mathcal{X})$ and $P_i \in \mathcal{P}_{n_i}(\mathcal{X}_i)$ ($1 \le i \le m$), we have
$$
S_{\mathcal{X}}(\mathcal{X}^{n})(P) = \frac{{n \choose nP}}{|\mathcal{X}|^n}
$$
$$
S_{\mathcal{X}_1 \cdots \mathcal{X}_m}(\prod_{i=1}^m A_i)(P_1, \cdots, P_m) = \prod_{i=1}^m S_{\mathcal{X}_i}(A_i)(P_i)
$$
where
$$
{n \choose nP} \eqdef \frac{n!}{\prod_{a \in \mathcal{X}} (nP(a))!}
$$
and $A_i \subseteq \mathcal{X}_i^{n_i}$ ($1 \le i \le m$).
\end{proposition}

\begin{proposition}\label{pr:SpectrumPropertyOfFunctions}
For any given random function $F: \mathcal{X}^n \to \mathcal{Y}^m$, we have
\begin{equation}\label{eq:SpectrumPropertyOfFunctions}
P\{\tilde{F}(\seq{x}) = \seq{y}\} = |\mathcal{Y}|^{-m} \alpha(F)(P_{\seq{x}}, P_{\seq{y}})
\end{equation}
for any $\seq{x} \in \mathcal{X}^n$ and $\seq{y} \in \mathcal{Y}^m$, where
\begin{equation}\label{eq:RandomizedF1}
\tilde{F} \eqdef \Sigma_m \circ F \circ \Sigma_n
\end{equation}
and
\begin{equation}
\alpha(F)(P, Q) \eqdef \frac{E[S_{\mathcal{X}\mathcal{Y}}(F)(P, Q)]}{S_{\mathcal{X}\mathcal{Y}}(\mathcal{X}^n \times \mathcal{Y}^m)(P, Q)}. \label{eq:DefinitionOfAlpha}
\end{equation}
\end{proposition}

\begin{remark}
For readers accustomed to thinking rather combinatorially than probabilistic, the following alternative expression for $P\{\tilde{F}(\seq{x}) = \seq{y}\}$ which is hidden in \eqref{eq:SpectrumPropertyOfFunctions} and \eqref{eq:DefinitionOfAlpha}, would be helpful: because of the symmetrization effect of uniform random permutations, $P\{\tilde{F}(\seq{x}) = \seq{y}\}$ depends only on the type-pair $(P,Q)=(P_{\seq{x}},P_{\seq{y}})$ of $(\seq{x},\seq{y})$ and equals the expected number of pairs $\bigl(\seq{x'},F(\seq{x}')\bigr)$ (``points of the graph of $F$'') of type-pair $(P,Q)$ divided by the total number of pairs $(\seq{x'},\seq{y}') \in \mathcal{X}^n \times \mathcal{Y}^m$ of type-pair $(P,Q)$. For a single encoding map $f$ it is just the fraction of pairs $(\seq{x'},\seq{y}') \in \mathcal{X}^n \times \mathcal{Y}^m$ of type-pair $(P,Q)$ which are points of the graph of $f$.
\end{remark}

\begin{proposition}\label{pr:GoodLinearCodes}
For any given linear code $f: \mathcal{X}^n \to \mathcal{Y}^m$, we have
\begin{equation}\label{eq:Identity2OfLC}
\alpha(f)(P_{0^n}, P_{\seq{y}}) = |\mathcal{Y}|^{m} 1\{\seq{y} = 0^m\}, \qquad \forall \seq{y} \in \mathcal{Y}^m.
\end{equation}
If both $\mathcal{X}$ and $\mathcal{Y}$ are the finite field $\field{q}$, we define a particular random linear code $\rlccode{q, n, m}: \field{q}^n \to \field{q}^m$ by $\seq{x} \mapsto \seq{x} \mat{A}_{n \times m}$, where $\mat{A}_{n \times m}$ denotes a random $n \times m$ matrix that is uniformly distributed over the set $\field{q}^{n \times m}$ of all $n \times m$ matrices over $\field{q}$. Then we have
\begin{equation}\label{eq:Identity1OfGLC}
P\{\rlccodetilde{q, n, m}(\seq{x}) = \seq{y}\} = P\{\rlccode{q, n, m}(\seq{x}) = \seq{y}\} = q^{-m}
\end{equation}
for all $\seq{x} \in \field{q}^n \backslash \{0^n\}$ and $\seq{y} \in \field{q}^m$, or equivalently
\begin{equation}\label{eq:Identity2OfGLC}
\alpha(\rlccode{q, n, m})(P, Q) = 1
\end{equation}
for all $P \in \mathcal{P}_n(\field{q}) \backslash \{P_{0^n}\}$ and $Q \in \mathcal{P}_m(\field{q})$.
\end{proposition}

\begin{proposition}\label{pr:IndependenceLC1}
For a given random linear code $F: \mathcal{X}^n \to \mathcal{Y}^m$, we have
\begin{IEEEeqnarray}{rCl}
P\{\hat{F}(\seq{x}) = \seq{y}\} &= &|\mathcal{Y}|^{-m} \label{eq:Identity1OfIndependenceLC1}\\
P\{\hat{F}(\hat{\seq{x}}) = \hat{\seq{y}} | \hat{F}(\seq{x}) = \seq{y}\}
&= &|\mathcal{Y}|^{-m} \alpha(F)(P_{\hat{\seq{x}}-\seq{x}}, P_{\hat{\seq{y}}-\seq{y}}) \label{eq:Identity2OfIndependenceLC1}
\end{IEEEeqnarray}
for any unequal $\seq{x}, \hat{\seq{x}} \in \mathcal{X}^n$ and any $\seq{y}, \hat{\seq{y}} \in \mathcal{Y}^m$, where
\begin{equation}\label{eq:RandomizedF2}
\hat{F}(\seq{x}) \eqdef \tilde{F}(\seq{x}) + \bar{Y}^m \qquad \forall \seq{x} \in \mathcal{X}^n
\end{equation}
and $\bar{Y}^m$ is an independent uniform random vector on $\mathcal{Y}^m$.
\end{proposition}


\section{Some New Methods and Results of the Code-Spectrum Approach}\label{sec:NewMethodsAndResultsOfCodeSpectrum}

In order to evaluate the performance of a linear code, we need to calculate or estimate its spectrum. However, the results established in \cite{JSCC:Yang200904} are still not enough for this purpose. So in this section, we shall present some new notions and methods to facilitate the calculation of spectra. For simplicity, some definitions and results are stated only for typical cases. Their extensions to more general cases are obvious and immediate, and hence will be used tacitly in subsequent derivations.

\subsection{Vector Permutations}\label{subsec:NewResultsI}

Given an $m$-tuple $\seqx{\sigma} = (\sigma_1,\ldots,\sigma_m) \in \prod_{i=1}^m \symmetricgroup{n_i}$, we define the \emph{vector permutation} as the Cartesian product $\bigpprod_{i=1}^m \sigma_i$ of permutation-induced automorphisms $\sigma_i: \mathcal{X}^{n_i} \to \mathcal{X}^{n_i}$, that is,
\[
\left(\bigpprod_{i=1}^m \sigma_i\right)(\seq{x}_{\mathcal{I}_m}) \eqdef (\sigma_i(\seq{x}_i))_{i \in \mathcal{I}_m} \qquad\forall \seq{x}_{\mathcal{I}_m} \in \prod_{i=1}^m \mathcal{X}^{n_i}.
\]
We denote this Cartesian product also by $\seqx{\sigma}$. Note that the vector permutation is by no means a Cartesian product of permutations. However, for convenience and also because we are only interested in Cartesian products of permutation-induced automorphisms, we shall abuse the term ``permutation'' for permutation-induced automorphisms when there is no possible ambiguity.

Define $\Sigma_{n_1,\ldots,n_m} \eqdef (\Sigma_{n_1},\ldots,\Sigma_{n_m})$, so that
$$
P\{\Sigma_{n_1,\ldots,n_m} = \seqx{\sigma}\} = \frac{1}{\prod_{i=1}^m n_i!} \qquad \forall \seqx{\sigma}\in \prod_{i=1}^m \symmetricgroup{n_i}.
$$
We obtain a uniformly distributed random vector permutation.

The next two propositions give some general properties of vector permutations.

\begin{proposition}\label{pr:SpectrumProperty1UnderVectorPermutation}
For any vector permutation $\seqx{\sigma} \in \prod_{i=1}^m \symmetricgroup{n_i}$ and any set $A \subseteq \prod_{i=1}^m \mathcal{X}_i^{n_i}$,
\begin{equation}
S_{\mathcal{X}_1 \cdots \mathcal{X}_m}(\seqx{\sigma}(A)) = S_{\mathcal{X}_1 \cdots \mathcal{X}_m}(A).
\end{equation}
\end{proposition}

\begin{proposition}\label{pr:SpectrumProperty2UnderVectorPermutation}
For any $\seq{x}_{\mathcal{I}_m} \in \prod_{i=1}^m \mathcal{X}_i^{n_i}$ and any random set $A \subseteq \prod_{i=1}^m \mathcal{X}_i^{n_i}$,
\begin{equation}\label{eq:SpectrumProperty21UnderVectorPermutation}
E\left[ \frac{1\{\seq{x}_{\mathcal{I}_m} \in \tilde{A}\}}{|A|} \right] = \frac{\alpha(A)((P_{\seq{x}_i})_{i \in \mathcal{I}_m})}{\prod_{i=1}^{m} |\mathcal{X}_i|^{n_i}}
\end{equation}
where
\begin{equation}
\tilde{A} \eqdef \Sigma_{n_1, \cdots, n_m}(A)
\end{equation}
and
\begin{equation}\label{eq:Definition2OfAlpha}
\alpha(A)((P_{\seq{x}_i})_{i \in \mathcal{I}_m}) \eqdef \frac{E[S_{\mathcal{X}_1 \cdots \mathcal{X}_m}(A)((P_{\seq{x}_i})_{i \in \mathcal{I}_m})]}{S_{\mathcal{X}_1 \cdots \mathcal{X}_m}(\prod_{i=1}^m \mathcal{X}_i^{n_i})((P_{\seq{x}_i})_{i \in \mathcal{I}_m})}.
\end{equation}
Moreover, for any nonnegative $l < m$ and any $P_i \in \mathcal{P}_{n_i}(\mathcal{X}_i)$ ($l+1 \le i \le m$),
\begin{IEEEeqnarray}{l}
E\left[ \frac{\left| \left( \seq{x}_{\mathcal{I}_l} \times \prod_{i=l+1}^m \mathcal{T}_{P_i}^{n_i}(\mathcal{X}_i) \right) \cap \tilde{A} \right|}{|A|} \right] \IEEEnonumber \\
\qquad = \frac{E[S_{\mathcal{X}_1 \cdots \mathcal{X}_m}(A)((P_{\seq{x}_i})_{i \in \mathcal{I}_l}, P_{\mathcal{I}_m \backslash \mathcal{I}_l})]}{\prod_{i=1}^l |\mathcal{X}_i|^{n_i} \prod_{i=1}^l S_{\mathcal{X}_i}(\mathcal{X}_i^{n_i})(P_{\seq{x}_i})}.\label{eq:SpectrumProperty22UnderVectorPermutation}
\end{IEEEeqnarray}
\end{proposition}

\begin{remark}\label{re:Relation1BetweenPropositions}
The identity \eqref{eq:SpectrumProperty21UnderVectorPermutation} can be rewritten as
$$
P\{\seq{x}_{\mathcal{I}_m} \in \tilde{A}\} = \frac{|A|}{\prod_{i=1}^{m} |\mathcal{X}_i|^{n_i}} \alpha(A)((P_{\seq{x}_i})_{i \in \mathcal{I}_m})
$$
whenever $|A|$ is a constant. For a given random function $F: \mathcal{X}^n \to \mathcal{Y}^m$, let $A = \mathrm{rl}(F)$ and note that $|A| = |\mathcal{X}|^n$, then it is obvious that Proposition~\ref{pr:SpectrumPropertyOfFunctions} is an easy consequence of Proposition~\ref{pr:SpectrumProperty2UnderVectorPermutation}. Generally, for a given random function $F: \prod_{i=1}^l \mathcal{X}_i^{n_i} \to \prod_{j=1}^k \mathcal{Y}_j^{m_j}$, we can define
$$
\tilde{F} \eqdef \Sigma_{m_1, \cdots, m_k} \circ F \circ \Sigma_{n_1, \cdots, n_l}.
$$
Clearly, $\mathrm{rl}(\tilde{F}) \eqvar{d} \widetilde{\mathrm{rl}(F)}$, and hence Proposition~\ref{pr:SpectrumProperty2UnderVectorPermutation} yields a generalized version of Proposition~\ref{pr:SpectrumPropertyOfFunctions}, that is,
\begin{IEEEeqnarray}{l}
P\{\tilde{F}(\seq{x}_{\mathcal{I}_l}) = \seq{y}_{\mathcal{I}_k}\} \IEEEnonumber\\
\qquad = \prod_{i=1}^k |\mathcal{Y}_i|^{-m_i} \cdot \alpha(F)((P_{\seq{x}_i})_{i \in \mathcal{I}_l}, (P_{\seq{y}_i})_{i \in \mathcal{I}_k}) \IEEEnonumber \\
\hspace{5em} \forall \seq{x}_{\mathcal{I}_l} \in \prod_{i=1}^l \mathcal{X}_i^{n_i}, \seq{y}_{\mathcal{I}_k} \in \prod_{j=1}^k \mathcal{Y}_j^{m_j} \label{eq:SpectrumProperty2OfFunctions}
\end{IEEEeqnarray}
where $\alpha(F) \eqdef \alpha(\mathrm{rl}(F))$.
\end{remark}

The proof of Proposition~\ref{pr:SpectrumProperty1UnderVectorPermutation} is omitted, while the proof of Proposition~\ref{pr:SpectrumProperty2UnderVectorPermutation} is presented in Section~\ref{subsec:ProofOfNewResultsI}.

\subsection{Codes and Conditional Probability Distributions}\label{subsec:NewResultsII}

In this subsection, we introduce one important notion that any code may be regarded as a conditional probability distribution. Such a viewpoint is very helpful when calculating the spectrum of a complex code consisting of many simple codes.

\begin{proposition}\label{pr:SpectrumPropertyX1OfFunctions}
For any random function $F: \prod_{i=1}^l \mathcal{X}_i^{n_i} \linebreak[0]\to \prod_{j=1}^k \mathcal{Y}_j^{m_j}$,
\begin{IEEEeqnarray}{l}
P\left\{\rtilde{F}(\seq{x}_{\mathcal{I}_l}) \in \prod_{j=1}^k \mathcal{T}_{Q_j}^{m_j}(\mathcal{Y}_j)\right\} \IEEEnonumber \\
\qquad = E[S_{\mathcal{Y}_1 \cdots \mathcal{Y}_k | \mathcal{X}_1 \cdots \mathcal{X}_l}(F)(Q_{\mathcal{I}_k}|(P_{\seq{x}_i})_{i \in \mathcal{I}_l})] \IEEEnonumber \\
\hspace{4em} \forall \seq{x}_{\mathcal{I}_l} \in \prod_{i=1}^l \mathcal{X}_i^{n_i}, Q_{\mathcal{I}_k} \in \prod_{j=1}^k \mathcal{P}_{m_j}(\mathcal{Y}_j) \label{eq:SpectrumPropertyX1OfFunctions}
\end{IEEEeqnarray}
where
\begin{equation}
\rtilde{F} \eqdef F \circ \Sigma_{n_1, \cdots, n_l}.
\end{equation}
\end{proposition}

\begin{remark}
The identity \eqref{eq:SpectrumPropertyX1OfFunctions} can also be rewritten as
\begin{IEEEeqnarray*}{l}
P\left\{\rtilde{F}(\seq{x}_{\mathcal{I}_l}) \in \prod_{j=1}^k \mathcal{T}_{Q_j}^{m_j}(\mathcal{Y}_j) \left| \seq{x}_{\mathcal{I}_l} \in \prod_{i=1}^l \mathcal{T}_{P_i}^{n_i}(\mathcal{X}_i) \right.\right\} \\
\qquad = E[S_{\mathcal{Y}_1 \cdots \mathcal{Y}_k | \mathcal{X}_1 \cdots \mathcal{X}_l}(F)(Q_{\mathcal{I}_k}|P_{\mathcal{I}_l})]
\end{IEEEeqnarray*}
which clearly indicates that the average forward conditional spectrum $E[S_{\mathcal{Y}_1 \cdots \mathcal{Y}_k | \mathcal{X}_1 \cdots \mathcal{X}_l}(F)(Q_{\mathcal{I}_k}|P_{\mathcal{I}_l})]$ may be regarded as the transition probability from $P_{\mathcal{I}_l}$ to $Q_{\mathcal{I}_k}$ under $\rtilde{F}$. This fundamental observation implies that coding modules like $\rtilde{F}$ or $\tilde{F}$ (instead of $F$) should be regarded as basic units in a coding system, and that the serial concatenation of such units may behave like the serial concatenation of conditional probability distributions. The following proposition proves this speculation.
\end{remark}

\begin{proposition}\label{pr:SpectrumOfSeriallyConcatenatedFunctions}
For any two random functions $F: \mathcal{X}^n \to \mathcal{Y}^m$ and $G: \mathcal{Y}^m \to \mathcal{Z}^l$,
\begin{IEEEeqnarray}{l}
E[S_{\mathcal{Z}|\mathcal{X}}(G \circ \Sigma_m \circ F)(Q|O)] \IEEEnonumber \\
\qquad = E[S_{\mathcal{Z}|\mathcal{X}}(\rtilde{G} \circ \rtilde{F})(Q|O)] \IEEEnonumber \\
\qquad = \sum_{P \in \mathcal{P}_m(\mathcal{Y})} E[S_{\mathcal{Y}|\mathcal{X}}(P|O)] E[S_{\mathcal{Z}|\mathcal{Y}}(Q|P)] \IEEEnonumber \\
\hspace{8em} \forall O \in \mathcal{P}_n(\mathcal{X}), Q \in \mathcal{P}_l(\mathcal{Z}).
\end{IEEEeqnarray}
\end{proposition}

The proofs of this subsection are given in Section~\ref{subsec:ProofOfNewResultsII}.

\subsection{Spectrum Generating Functions}\label{subsec:NewResultsIIIpre}

The \emph{spectrum generating function} of a set $A \subseteq \mathcal{X}^n$ is a polynomial in $|\mathcal{X}|$ indeterminates, whose coefficients form the spectrum of $A$. As an element of $\complexnumbers[u_a; a \in \mathcal{X}]$ it can be succinctly defined as
\begin{IEEEeqnarray*}{rCl}
\mathcal{G}_\mathcal{X}(A)(\seq{u})
&\eqdef &\frac{1}{|A|} \sum_{\seq{x} \in A} \prod_{i=1}^n u_{x_i} \\
&= &\sum_{P \in \mathcal{P}_n(\mathcal{X})} \left(S_{\mathcal{X}}(A)(P) \prod_{a\in \mathcal{X}} u_{a}^{nP(a)}\right)
\end{IEEEeqnarray*}
where $\seq{u} \eqdef (u_a)_{a \in \mathcal{X}}$. For convenience, we shall write $\seq{u}^{nP}$ in place of $\prod_{a \in \mathcal{X}} u_a^{nP(a)}$ in the sequel.

We can associate similar generating functions with other types of spectra defined in Section~\ref{sec:BasicsOfCodeSpectrumApproach}, the most important of which is the joint-spectrum generating function of a set $B \subseteq \mathcal{X}^n \times \mathcal{Y}^m$:
\begin{IEEEeqnarray*}{l}
\mathcal{G}_{\mathcal{X}\mathcal{Y}}(B)(\seq{u},\seq{v}) \\
\findent \eqdef \sum_{\substack{P\in\mathcal{P}_n(\mathcal{X})\\ Q\in\mathcal{P}_m(\mathcal{Y})}}
  S_{\mathcal{XY}}(B)(P,Q) \cdot \seq{u}^{nP} \seq{v}^{mQ} \\
\findent = \frac{1}{|B|}\sum_{(\seq{x},\seq{y})\in B} \seq{u}^{nP_{\seq{x}}} \seq{v}^{mP_{\seq{y}}} \in \complexnumbers[u_a,v_b; a\in\mathcal{X}, b\in\mathcal{Y}],
\end{IEEEeqnarray*}
a polynomial in the $|\mathcal{X}|+|\mathcal{Y}|$ indeterminates $u_a$, $a\in\mathcal{X}$, and $v_b$, $b\in\mathcal{Y}$, where $\seq{u} \eqdef (u_a)_{a \in \mathcal{X}}$ and $\seq{v} \eqdef (v_b)_{b \in \mathcal{Y}}$.

To simplify notations, we sometimes write $\mathcal{G}(A)(\seq{u})$ and $\mathcal{G}(B)(\seq{u},\seq{v})$ when there is no possible ambiguity.

When the set $A \subseteq \mathcal{X}^n$ is random, its associated spectrum generating function is also random. To analyze a random polynomial, we need to consider its expectation. However, the expectation of a random polynomial is indeed undefined in the usual sense of expectations, so it is necessary to give its definition formally. Let $\complexnumbers[u_a; a \in A]$ be a ring of polynomials, where $A$ is a nonempty finite set. Since the ring is a subset of $\complexnumbers^{\nnintegers^A}$, namely, all mappings of $\nnintegers^A$ into $\complexnumbers$, it can be endowed with the $\sigma$-algebra $\mathcal{S} \eqdef \complexnumbers[u_a; a \in A] \cap \mathcal{B}^{\nnintegers^A}$ where $\mathcal{B}$ is the Borel $\sigma$-algebra of $\complexnumbers$. For a given random polynomial $P(\seq{u}): \Omega \to \complexnumbers[u_a; a \in A]$, its expectation is defined as
\[
E[P(\seq{u})] \eqdef \sum_{\seq{n} \in \nnintegers^A} E[\coef{P(\seq{u}), \seq{u}^{\seq{n}}}] \cdot \seq{u}^\seq{n}
\]
where $\coef{p(\seq{u}), \seq{u}^{\seq{n}}}$ denotes the coefficient of the monomial $\seq{u}^{\seq{n}}$ in $p(\seq{u})$. To see that it is well defined, note that $\coef{p(\seq{u}), \seq{u}^{\seq{n}}}$ with $\seq{n}$ fixed is a canonical projection from $\complexnumbers^{\nnintegers^A}$ to $\complexnumbers$ and hence measurable. Analogous to ordinary expectations, expectations of random polynomials have the following properties: for any random polynomials $P_1(\seq{u})$ and $P_2(\seq{u})$,
\[
E[P_1(\seq{u})+P_2(\seq{u})] = E[P_1(\seq{u})] + E[P_2(\seq{u})];
\]
if $P_1(\seq{u})$ and $P_2(\seq{u})$ are independent then
\[
E[P_1(\seq{u}) P_2(\seq{u})] = E[P_1(\seq{u})] E[P_2(\seq{u})].
\]
We leave the proofs to the reader. The next proposition gives an important property of expectations of random spectrum generating functions.

\begin{proposition}\label{pr:RenameGeneratingFunction}
Let $F: \mathcal{X} \to \mathcal{X}$ and $G: \mathcal{Y} \to \mathcal{Y}$ be two independent random bijective mappings. Then for any random set $B \subseteq \mathcal{X}^n \times \mathcal{Y}^m$, the expectation $E[\mathcal{G}((F_n \pprod G_m)(B))(\seq{u}, \seq{v})]$ can be obtained from $E[\mathcal{G}(B)(\seq{u}, \seq{v})]$ by the substitutions
\begin{equation}\label{eq:RenameSubstitutionRuleX}
u_{a} \mapsto E[u_{F(a)}] \qquad \forall a \in \mathcal{X}
\end{equation}
and
\begin{equation}\label{eq:RenameSubstitutionRuleY}
v_{b} \mapsto E[v_{G(b)}] \qquad \forall b \in \mathcal{Y}
\end{equation}
where $F_n \eqdef \bigpprod_{i=1}^n F$ and $G_m \eqdef \bigpprod_{j=1}^m G$.
\end{proposition}

The proof is given in Section~\ref{subsec:ProofOfNewResultsIIIpre}.


\subsection{Spectra with Coordinate Partitions}\label{subsec:NewResultsIII}

In Section~\ref{subsec:NewResultsII}, we introduced the method for calculating the spectra of serial concatenations of codes. In this subsection, we proceed to investigate the other important kind of combinations of codes, namely, parallel concatenations. To cope with the problem involving concatenations (products) of sequences, we first need to introduce a generalized definition of spectra, namely, spectra of sets with coordinate partitions.

Let $A$ be a subset of $\mathcal{X}^n$, with coordinate set $\mathcal{I}_n$. Let $\mathcal{U}$ be a fixed partition of $\mathcal{I}_n$, namely, a set of nonempty subsets of $\mathcal{I}_n$ such that every number in $\mathcal{I}_n$ is in exactly one of these subsets. We define the \emph{$\mathcal{U}$-type} $P^{\mathcal{U}}_{\seq{x}}$ of a sequence $\seq{x} \in \mathcal{X}^n$ as
$$
(P^{U}_{\seq{x}})_{U \in \mathcal{U}} \eqdef (P_{x_{U}})_{U \in \mathcal{U}}.
$$
By $\mathcal{P}^{\mathcal{U}}_n(\mathcal{X})$ we mean the set of all $\mathcal{U}$-types of sequences in $\mathcal{X}^n$, so that
$$
\mathcal{P}^{\mathcal{U}}_n(\mathcal{X}) = \prod_{U \in \mathcal{U}} \mathcal{P}_{|U|}(\mathcal{X}).
$$
Any $\mathcal{U}$-type in $\mathcal{P}^{\mathcal{U}}_n(\mathcal{X})$ is denoted in the form $P^{\mathcal{U}} \eqdef (P^{U})_{U \in \mathcal{U}}$. Based on the $\mathcal{U}$-type, we define the \emph{$\mathcal{U}$-spectrum} of $A$ as the empirical distribution $S_{\mathcal{X}^{\mathcal{U}}}(A)$ on $\mathcal{P}^{\mathcal{U}}_n(\mathcal{X})$ given by
$$
S_{\mathcal{X}^\mathcal{U}}(A)(P^{\mathcal{U}}) \eqdef \frac{|\{ \seq{x} \in A | P^{\mathcal{U}}_{\seq{x}} = P^{\mathcal{U}} \}|}{|A|} \qquad \forall P^{\mathcal{U}} \in \mathcal{P}^{\mathcal{U}}_n(\mathcal{X}).
$$
The $\mathcal{U}$-spectrum is just a variant of the joint spectrum. When $\mathcal{U} = \{ \mathcal{I}_n \}$, it reduces to the ordinary spectrum.

Analogously, given a set $B \subseteq \mathcal{X}^n \times \mathcal{Y}^m$ and a pair of coordinate partitions $\mathcal{U}$ of $\mathcal{I}_n$ and $\mathcal{V}$ of $\mathcal{I}_m$, we can define the joint $(\mathcal{U}, \mathcal{V})$-spectrum $S_{\mathcal{X}^{\mathcal{U}}\mathcal{Y}^{\mathcal{V}}}(B)$ on $\mathcal{P}^{\mathcal{U}}_n(\mathcal{X}) \times \mathcal{P}^{\mathcal{V}}_m(\mathcal{Y})$. Furthermore, given the function $f: \mathcal{X}^n \to \mathcal{Y}^m$ with a pair of coordinate partitions $(\mathcal{U}, \mathcal{V})$, we define its joint $(\mathcal{U}, \mathcal{V})$-spectrum $S_{\mathcal{X}^{\mathcal{U}}\mathcal{Y}^{\mathcal{V}}}(f)$ as the joint $(\mathcal{U}, \mathcal{V})$-spectrum of its associated relation $\mathrm{rl}(f)$. Similar generalizations follow easily for conditional and marginal spectra.

The above concepts are crucial for computing the spectra of parallel concatenations of codes, but the notations are somewhat complex. For convenience, when we explicitly write $A \subseteq \prod_{i=1}^p \mathcal{X}^{n_i}$ with $\sum_{i=1}^p n_i = n$, we tacitly assume that the default coordinate partition is
\begin{IEEEeqnarray}{rCl}
\mathcal{U}_0 &\eqdef &\{U_1, U_2, \cdots, U_p\} \IEEEnonumber \\
&= &\left\{ \{1,\cdots,n_1\}, \cdots, \left\{\sum_{i=1}^{p-1} n_i + 1, \cdots, n\right\} \right\}. \label{eq:DefinitionOfDefaultCoordinatePartition}
\end{IEEEeqnarray}
Thus the default spectrum of $A$ is the $\mathcal{U}_0$-spectrum of $A$ and is denoted by $S_{\mathcal{X}\cdots\mathcal{X}}(A)$ or $S_{\mathcal{X}^p}(A)$. When $p = 1$, this convention just coincides with the ordinary spectrum of $A$.

Now, even for a single set $A \subseteq \mathcal{X}^n$, there are many different spectra of $A$ with respect to different coordinate partitions. So next, let us investigate the properties of spectra of sets with coordinate partitions. For this purpose, we need to generalize the spectrum generating functions introduced in Section~\ref{subsec:NewResultsIIIpre}.

For any set $A \subseteq \mathcal{X}^n$ with a coordinate partition $\mathcal{U}$, we define its \emph{$\mathcal{U}$-spectrum generating function} $\mathcal{G}_{\mathcal{X}^{\mathcal{U}}}(A)$ as
\begin{IEEEeqnarray*}{rCl}
\mathcal{G}_{\mathcal{X}^{\mathcal{U}}}(A)(\seq{u}_{\mathcal{U}})
&\eqdef &\frac{1}{|A|} \sum_{\seq{x} \in A} \prod_{U \in \mathcal{U}} \seq{u}_U^{|U|P^{U}_{\seq{x}}} \\
&= &\sum_{P^{\mathcal{U}} \in \mathcal{P}^{\mathcal{U}}_n(\mathcal{X})} S_{\mathcal{X}^{\mathcal{U}}}(A)(P^{\mathcal{U}}) \prod_{U \in \mathcal{U}} \seq{u}_U^{|U|P^{U}}
\end{IEEEeqnarray*}
a polynomial in the $|\mathcal{U}| |\mathcal{X}|$ indeterminates $u_{U,a}$, $U \in \mathcal{U}$, $a \in \mathcal{X}$, where $\seq{u}_{\mathcal{U}} \eqdef (\seq{u}_{U})_{U \in \mathcal{U}} = (u_{U,a})_{U \in \mathcal{U}, a \in \mathcal{X}}$. When $\mathcal{U} = \{\mathcal{I}_n\}$, this definition reduces to the ordinary spectrum generating function $\mathcal{G}_{\mathcal{X}}(A)(\seq{u})$.

Analogously, given a set $B \subseteq \mathcal{X}^n \times \mathcal{Y}^m$ with coordinate partitions $\mathcal{U}$ and $\mathcal{V}$, we can define the $(\mathcal{U}, \mathcal{V})$-spectrum generating function $\mathcal{G}_{\mathcal{X}^{\mathcal{U}}\mathcal{Y}^{\mathcal{V}}}(B)(\seq{u}_{\mathcal{U}}, \seq{v}_{\mathcal{V}})$. And furthermore, given a function $f: \mathcal{X}^n \to \mathcal{Y}^m$ with coordinate partitions $\mathcal{U}$ and $\mathcal{V}$, we define its $(\mathcal{U}, \mathcal{V})$-spectrum generating function by
$$
\mathcal{G}_{\mathcal{X}^{\mathcal{U}}\mathcal{Y}^{\mathcal{V}}}(f)(\seq{u}_{\mathcal{U}}, \seq{v}_{\mathcal{V}}) \eqdef \mathcal{G}_{\mathcal{X}^{\mathcal{U}}\mathcal{Y}^{\mathcal{V}}}(\mathrm{rl}(f))(\seq{u}_{\mathcal{U}}, \seq{v}_{\mathcal{V}}).
$$

Again for convenience, when we explicitly write $A \subseteq \prod_{i=1}^p \mathcal{X}^{n_i}$ with $\sum_{i=1}^p n_i = n$, we tacitly assume that the default coordinate partition is $\mathcal{U}_0$ defined by \eqref{eq:DefinitionOfDefaultCoordinatePartition}. Thus the default spectrum generating function of $A$ is its $\mathcal{U}_0$-spectrum generating function which we denote by $\mathcal{G}_{\mathcal{X}\cdots\mathcal{X}}(A)(\seq{u}_1, \cdots, \seq{u}_p)$ or $\mathcal{G}_{\mathcal{X}^p}(A)(\seq{u}_{\mathcal{I}_p})$. When $p = 1$, it coincides with the notation $\mathcal{G}_{\mathcal{X}}(A)(\seq{u})$.

Based on the above definitions, we proved the following properties:

\begin{proposition}\label{pr:GeneratingFunctionOfProductOfSets}
For any sets $A \subseteq \mathcal{X}^n$ and $B \subseteq \mathcal{Y}^m$,
\begin{equation}
\mathcal{G}(A \times B)(\seq{u}, \seq{v}) = \mathcal{G}(A)(\seq{u}) \cdot \mathcal{G}(B)(\seq{v}).
\end{equation}
\end{proposition}

\begin{proposition}\label{pr:SubstitutionPrincipleOfGeneratingFunction}
Suppose $\mathcal{U}_1$ and $\mathcal{U}_2$ are two partitions of $\mathcal{I}_n$. If $\mathcal{U}_2$ is a refinement of $\mathcal{U}_1$ (which means each element of $\mathcal{U}_1$ is a union of elements of $\mathcal{U}_2$), then $\mathcal{G}_{\mathcal{X}^{\mathcal{U}_1}}(A)(\seq{u}_{1,\mathcal{U}_1})$ can be obtained from $\mathcal{G}_{\mathcal{X}^{\mathcal{U}_2}}(A)(\seq{u}_{2,\mathcal{U}_2})$ by the substitution
\begin{equation}\label{eq:SubstitutionRule}
\seq{u}_{2,U_2} \mapsto \seq{u}_{1,U_1} \qquad \mbox{if } U_{2} \subseteq U_{1}
\end{equation}
where $U_1 \in \mathcal{U}_1$ and $U_2 \in \mathcal{U}_2$.
\end{proposition}

By Propositions~\ref{pr:GeneratingFunctionOfProductOfSets} and \ref{pr:SubstitutionPrincipleOfGeneratingFunction}, we easily obtain a series of corollaries as follows.

\begin{corollary}\label{co:GeneratingFunctionOfSetProduct}
For any two sets $A_1 \subseteq \mathcal{X}^{n_1}$ and $A_2 \subseteq \mathcal{X}^{n_2}$, we have
$$
\mathcal{G}_{\mathcal{X}}(A_1 \times A_2)(\seq{u}) = \mathcal{G}_{\mathcal{X}}(A_1)(\seq{u}) \cdot \mathcal{G}_{\mathcal{X}}(A_2)(\seq{u}).
$$
\end{corollary}

\begin{corollary}\label{co:GeneratingFunctionOfSpace}
$$
\mathcal{G}(\mathcal{X}^n)(\seq{u}) = [\mathcal{G}(\mathcal{X})(\seq{u})]^n = \left( \frac{\sum_{a \in \mathcal{X}} u_a}{|\mathcal{X}|} \right)^n.
$$
\end{corollary}

\begin{corollary}\label{co:GeneratingFunctionOfFunctionParallelProduct}
For any two maps $f_1: \mathcal{X}^{n_1} \to \mathcal{Y}^{m_1}$ and $f_2: \mathcal{X}^{n_2} \to \mathcal{Y}^{m_2}$, we have
$$
\mathcal{G}_{\mathcal{X}\mathcal{Y}}(f_1 \pprod f_2)(\seq{u}, \seq{v}) = \mathcal{G}_{\mathcal{X}\mathcal{Y}}(f_1)(\seq{u}, \seq{v}) \cdot \mathcal{G}_{\mathcal{X}\mathcal{Y}}(f_2)(\seq{u}, \seq{v}).
$$
\end{corollary}

The proofs of Corollary~\ref{co:GeneratingFunctionOfSpace} are omitted, while the proofs of the other results are given in Section~\ref{subsec:ProofOfNewResultsIII}. Note that Corollary~\ref{co:GeneratingFunctionOfSpace} is an easy consequence of Corollary~\ref{co:GeneratingFunctionOfSetProduct}, and that Corollary~\ref{co:GeneratingFunctionOfFunctionParallelProduct} is just the tool that we want for  computing the spectra of parallel concatenations of codes.


\subsection{MacWilliams Identities}\label{subsec:NewResultsV}

One of the most famous results in coding theory is the MacWilliams identities \cite{JSCC:MacWilliams196300}, which relate the weight enumerator of a linear code to that of its dual code. In this subsection, we shall generalize this result in the framework of code-spectrum approach. This generalization may be regarded as a combination and extension of the results in \cite{JSCC:Wood199903,JSCC:Simonis199502,JSCC:Honold200100}.

To make things easier to understand, we shall mainly consider the special case that the alphabet is a finite field $\field{q}$ with $q = p^r$, where $p$ is prime.

For any $\seq{x}_1, \seq{x}_2 \in \field{q}^n$, we define the standard dot product on $\field{q}^n$ by
$$
\seq{x}_1 \cdot \seq{x}_2 = \sum_{i=1}^n x_{1,i} x_{2,i}.
$$
Then for any set $A \subseteq \field{q}^n$, the \emph{orthogonal set} $A^{\perp}$ of $A$ is given by
$$
A^{\perp} = \{\seq{x} \in \field{q}^n | \forall \seq{x}' \in A: \seq{x} \cdot \seq{x}' = 0 \}.
$$
Clearly, $A^{\perp}$ is a subspace of $\field{q}^n$.

The next theorem gives the generalized MacWilliams identities in the framework of code-spectrum approach.

\begin{theorem}\label{th:MacWilliamsIdentitiesF}
Let $A$ be a subspace of $\field{q}^n$ and $\mathcal{U}$ a fixed partition of $\mathcal{I}_n$. Then
\begin{equation}\label{eq:MacWilliamsIdentitiesF}
\mathcal{G}_{\field{q}^\mathcal{U}}(A^{\perp})(\seq{u}_{\mathcal{U}}) = \frac{1}{|A^{\perp}|} \mathcal{G}_{\field{q}^\mathcal{U}}(A)((\seq{u}_U \mat{M})_{U \in \mathcal{U}})
\end{equation}
where $\mat{M}$ is the $q \times q$ matrix (indexed by the elements of $\field{q}$) defined by
\begin{equation}\label{eq:MacWilliamsMatrixF}
\matentry{M}_{a_1, a_2} = \chi(a_1 a_2) \qquad \forall a_1, a_2 \in \field{q}
\end{equation}
\begin{equation}
\chi(x) \eqdef e^{2\pi i \mathrm{Tr}(x)/p}
\end{equation}
\begin{equation}
\mathrm{Tr}(x) \eqdef x+x^p+\cdots+x^{p^{r-1}}.
\end{equation}
\end{theorem}

\begin{remark}
Note that $\mathrm{Tr}(x)$ is an $\field{p}$-module epimorphism from $\field{q}$ onto $\field{p}$, and hence $\chi(x)$ is a homomorphism from the additive group of $\field{q}$ to $\unitsof{\complexnumbers}$. Moreover, it is easy to see that
\begin{equation}
\sum_{x \in \field{q}} \chi(ax) = \sum_{x \in \field{q}} \chi(x) = 0 \qquad \forall a \ne 0.\label{eq:ChiPropertyF}
\end{equation}
From this fact, it follows that $q^{-\frac{1}{2}}\mat{M}$ is a symmetric, unitary matrix. In particular,
\begin{equation}\label{eq:MacWilliamsMatrixPropertyF}
\sum_{x \in \field{q}} M_{a,x} = \sum_{x \in \field{q}} M_{x,a} = q 1\{a = 0\}.
\end{equation}
\end{remark}

One important application of Theorem~\ref{th:MacWilliamsIdentitiesF} is calculating the joint spectrum of a linear code $\seq{x} = \seq{y} \transpose{\mat{A}}$ when the joint spectrum of $\seq{y} = \seq{x}\mat{A}$ is known. The next theorem gives the details.

\begin{theorem}\label{th:MacWilliamsIdentitiesJF}
Let $\mat{A}$ be an $n \times m$ matrix over $\field{q}$. Define the linear codes $f: \field{q}^n \to \field{q}^m$ and $g: \field{q}^m \to \field{q}^n$ by
\begin{equation}\label{eq:MacWilliamsIdentitiesJfF}
f(\seq{x}) = \seq{x} \mat{A} \qquad \forall \seq{x} \in \field{q}^n
\end{equation}
and
\begin{equation}\label{eq:MacWilliamsIdentitiesJgF}
g(\seq{y}) = \seq{y} \transpose{\mat{A}} \qquad \forall \seq{y} \in \field{q}^m
\end{equation}
respectively. Let $\mathcal{U}$ be a partition of $\mathcal{I}_n$ and $\mathcal{V}$ a partition of $\mathcal{I}_m$. Then
\begin{IEEEeqnarray}{l}
\mathcal{G}_{\field{q}^\mathcal{V}\field{q}^{\mathcal{U}}}(-g)(\seq{v}_{\mathcal{V}}, \seq{u}_{\mathcal{U}}) = \IEEEnonumber \\
\findent \frac{1}{q^m} \mathcal{G}_{\field{q}^\mathcal{U}\field{q}^{\mathcal{V}}}(f)((\seq{u}_U \mat{M})_{U \in \mathcal{U}}, (\seq{v}_V \mat{M})_{V \in \mathcal{V}}) \label{eq:MacWilliamsIdentitiesJ}
\end{IEEEeqnarray}
where $\mat{M}$ is the matrix defined by \eqref{eq:MacWilliamsMatrixF}.
\end{theorem}

The above results can be further generalized by replacing $\field{q}$ and $\chi$ with a Frobenius ring and its generating character, respectively. A ring $\mathcal{X}$ is said to be a \emph{Frobenius ring} if there exists a group homomorphism $\chi: (\mathcal{X},+) \to \nonzerocomplexnumbers$ (\emph{character} of $(\mathcal{X},+)$), whose kernel contains no nonzero ideal. Such a homomorphism is called a \emph{generating character} of $\mathcal{X}$. For background information on Frobenius rings and their uses in coding theory we refer to \cite{JSCC:Honold200106}, \cite[\S 16]{JSCC:Lam1999}, \cite{JSCC:Nechaev200800}, and \cite{JSCC:Wood199903}.

\begin{theorem}[cf. also \cite{JSCC:Honold200100}]\label{th:MacWilliamsIdentities}
Let $\mathcal{X}$ be a Frobenius ring, $A$ a submodule of $\mathcal{X}^n$, and $\mathcal{U}$ a fixed partition of $\mathcal{I}_n$. We have
\begin{equation}\label{eq:MacWilliamsIdentities}
\mathcal{G}_{\mathcal{X}^\mathcal{U}}(A^{\perp})(\seq{u}_{\mathcal{U}}) = \frac{1}{|A^{\perp}|} \mathcal{G}_{\mathcal{X}^\mathcal{U}}(A)((\seq{u}_U \mat{M})_{U \in \mathcal{U}})
\end{equation}
where $\mat{M}$ is the $|\mathcal{X}| \times |\mathcal{X}|$ matrix (indexed by the elements of $\mathcal{X}$) defined by
\begin{equation}\label{eq:MacWilliamsMatrix}
\matentry{M}_{a_1, a_2} = \chi(a_1 a_2) \qquad \forall a_1, a_2 \in \mathcal{X}
\end{equation}
for some generating character $\chi$ of $\mathcal{X}$.
\end{theorem}

The proofs of this subsection are given in Section \ref{subsec:ProofOfNewResultsV}.



\section{Good Linear Codes for Source Coding, Channel Coding, and Joint Source-Channel Coding}\label{sec:ConceptsOfGoodLinearCodes}

In the world of classical coding theory, a good linear code always means a set of codewords that has good performance for some family of channels or has some good distance properties (e.g., the Singleton bound, the Gilbert-Varshamov bound, and so on). Such a viewpoint may be enough for channel coding, but may have its limitations in the context of source coding and JSCC. This is mainly because the approach only regarding linear codes as a set of codewords cannot cover all the properties of linear codes, and in different applications there are different criteria for good linear codes.

In \cite[Table~I]{JSCC:Yang200904}, we only briefly reviewed the criteria of good linear codes in terms of spectrum requirements for lossless source coding, channel coding, and lossless JSCC. So in this section, we shall resume this discussion, including the concepts of good linear codes and the relations among different kinds of good linear codes.

At first, let us introduce some concepts about rates of codes.

For any linear code $f: \mathcal{X}^n \to \mathcal{Y}^m$, we define the \emph{source transmission rate} $R_s(f)$ (nats per source symbol) of $f$ by
\begin{equation}
R_s(f) \eqdef \frac{1}{n} \ln |f(\mathcal{X}^n)|.
\end{equation}
Analogously, we define the \emph{channel transmission rate} $R_c(f)$ (nats per channel symbol) of $f$ by
\begin{equation}
R_c(f) \eqdef \frac{1}{m} \ln |f(\mathcal{X}^n)|.
\end{equation}
Recall that in Section~\ref{sec:BasicsOfCodeSpectrumApproach}, we define the (coding) rate $R(f)$ of a linear code $f$ by $n/m$. Then there is a simple relation among $R_s(f)$, $R_c(f)$, and $R(f)$, that is, $R(f)R_s(f) = R_c(f)$. If $f$ is injective, then $R_s(f) = \ln|\mathcal{X}|$ and $R_c(f) = \ln|\mathcal{X}| R(f)$; if $f$ is surjective, then $R_s(f) = \ln|\mathcal{Y}|/R(f)$ and $R_c(f) = \ln|\mathcal{Y}|$.

Let $\seqx{F} = \{F_k: \mathcal{X}^{n_k} \to \mathcal{Y}^{m_k}\}_{k=1}^\infty$ be a sequence of random linear codes. We define the \emph{asymptotic supremum source transmission rate} $\overline{R}_s(\seqx{F})$ and the \emph{asymptotic infimum source transmission rate} $\underline{R}_s(\seqx{F})$ by $\overline{R}_s(\seqx{F}) \eqdef \plimsup_{k \to \infty} R_s(F_k)$ and $\underline{R}_s(\seqx{F}) \eqdef \pliminf_{k \to \infty} R_s(F_k)$, respectively. As $\overline{R}_s(\seqx{F}) = \underline{R}_s(\seqx{F})$, we say that the \emph{asymptotic source transmission rate} of $\seqx{F}$ is
\begin{equation}
R_s(\seqx{F}) \eqdef \plim_{k \to \infty} R_s(F_k).
\end{equation}
Analogously, we define the \emph{asymptotic supremum channel transmission rate} $\overline{R}_c(\seqx{F})$ and the \emph{asymptotic infimum channel transmission rate} $\underline{R}_c(\seqx{F})$ by $\overline{R}_c(\seqx{F}) \eqdef \plimsup_{k \to \infty} R_c(F_k)$ and $\underline{R}_c(\seqx{F}) \eqdef \pliminf_{k \to \infty} R_c(F_k)$, respectively. As $\overline{R}_c(\seqx{F}) = \underline{R}_c(\seqx{F})$, we say that the \emph{asymptotic channel transmission rate} of $\seqx{F}$ is
\begin{equation}
R_c(\seqx{F}) \eqdef \plim_{k \to \infty} R_c(F_k).
\end{equation}
Also, we define the \emph{asymptotic supremum coding rate} $\overline{R}(\seqx{F})$ and the \emph{asymptotic infimum coding rate} $\underline{R}(\seqx{F})$ by $\overline{R}(\seqx{F}) \eqdef \limsup_{k \to \infty} R(F_k)$ and $\underline{R}(\seqx{F}) \eqdef \liminf_{k \to \infty} R(F_k)$, respectively. As $\overline{R}(\seqx{F}) = \underline{R}(\seqx{F})$, we say that the \emph{asymptotic coding rate} of $\seqx{F}$ is
\begin{equation}
R(\seqx{F}) \eqdef \lim_{k \to \infty} R(F_k).
\end{equation}

To simplify notations, in the rest of this section, when writing $\seqx{F}$, we always mean a sequence $\{F_k\}_{k=1}^\infty$ of random linear codes $F_k: \mathcal{X}^{n_k} \to \mathcal{Y}^{m_k}$. To avoid some singular cases, we assume in the sequel that for any sequence $\seqx{F}$ of random linear codes, $\lim_{k \to \infty} |F_k(\mathcal{X}^{n_k})| = \infty$.

Next, for better understanding of the definitions of good linear codes, let us review the original requirements of good linear codes for lossless source coding, channel coding, and lossless JSCC, respectively.\footnote{This review is merely based on the ideas and results in previous papers. For technical reasons, the requirements we give here are not the same as those in the literature.}

According to \cite{JSCC:Yang200503}, a sequence $\seqx{F}$ of random linear codes with the asymptotic source transmission rate $R_s(\seqx{F})$ is said to be $\delta$-asymptotically good for lossless source coding if for any $\epsilon > 0$ there exits a sequence of events $A_k \in \mathcal{A}$ such that for sufficiently large $k$,
\begin{equation}
P(A_k) \ge 1 - \epsilon \label{eq:OriginalDefinitionX1OfAsympGoodLSC} \\
\end{equation}
\begin{equation}
|R_s(F_k) - R_s(\seqx{F})| \le \epsilon \qquad \forall \omega \in A_k \label{eq:OriginalDefinitionX2OfAsympGoodLSC}
\end{equation}
\begin{equation}
\max_{\seq{x}, \hat{\seq{x}}: \seq{x} \ne \hat{\seq{x}}} \frac{1}{n_k} \ln P\{F_k(\seq{x}) = F_k(\hat{\seq{x}}) | A_k \} \le -R_s(\seqx{F}) + \delta + \epsilon. \label{eq:OriginalDefinitionOfAsympGoodLSC}
\end{equation}
Note that
$$
\lim_{k \to \infty} P\{|R_s(F_k) - R_s(\seqx{F})| \le \epsilon\} = 1
$$
so this definition is reasonable. Due to the property of linear codes, the condition \eqref{eq:OriginalDefinitionOfAsympGoodLSC} is equivalent to
\begin{equation}
\max_{\seq{x}: \seq{x} \ne 0^{n_k}} \frac{1}{n_k} \ln P\{\seq{x} \in \ker F_k | A_k \} \le -R_s(\seqx{F}) + \delta + \epsilon. \label{eq:OriginalDefinition2OfAsympGoodLSC}
\end{equation}

According to \cite{JSCC:Gallager196800,JSCC:Shulman199909,JSCC:Bennatan200403}, a sequence $\seqx{F}$ of random linear codes with the asymptotic channel transmission rate $R_c(\seqx{F})$ is said to be $\delta$-asymptotically good for channel coding if for any $\epsilon > 0$ there exits a sequence of events $A_k \in \mathcal{A}$ such that for sufficiently large $k$,
\begin{equation}
P(A_k) \ge 1 - \epsilon \label{eq:OriginalDefinitionX1OfAsympGoodLCC} \\
\end{equation}
\begin{equation}
|R_c(F_k) - R_c(\seqx{F})| \le \epsilon \qquad \forall \omega \in A_k \label{eq:OriginalDefinitionX2OfAsympGoodLCC}
\end{equation}
\begin{equation}\label{eq:OriginalDefinitionOfAsympGoodLCC}
\max_{\seq{y}, \hat{\seq{y}}: \seq{y} \ne \hat{\seq{y}}} \frac{1}{m_k} \ln \left( \frac{P\{\seq{y} \in \mathcal{C}_{F_k}, \hat{\seq{y}} \in \mathcal{C}_{F_k} | A_k\}}{P\{\seq{y} \in \mathcal{C}_{F_k} | A_k\} P\{\hat{\seq{y}} \in \mathcal{C}_{F_k} | A_k\}} \right) \le \delta + \epsilon
\end{equation}
where $\mathcal{C}_{F_k} \eqdef F_k(\mathcal{X}^{n_k}) + \bar{Y}^{m_k}$ and $\bar{Y}^{m_k}$ is an independent uniform random vector on $\mathcal{Y}^{m_k}$. Clearly,
$$
\left| \frac{1}{m_k} \ln P\{\seq{y} \in \mathcal{C}_{F_k} | A_k\} + \ln |\mathcal{Y}| - R_c(\seqx{F}) \right| \le \epsilon
$$
for all $\seq{y} \in \mathcal{Y}^{m_n}$.
Because $F_k$ is a linear code, we also have
\begin{IEEEeqnarray*}{l}
P\{\seq{y} \in \mathcal{C}_{F_k}, \hat{\seq{y}} \in \mathcal{C}_{F_k} | A_k\} \\
\findent = P\{\seq{y} \in \mathcal{C}_{F_k}, \hat{\seq{y}} - \seq{y} \in F_k(\mathcal{X}^{n_k}) | A_k\} \\
\findent = \sum_{f_k} P\{F_k = f_k | A_k\} E[1\{\seq{y} \in \mathcal{C}_{f_k}, \hat{\seq{y}} - \seq{y} \in f_k(\mathcal{X}^{n_k})\}] \\
\findent = \sum_{f_k} P\{F_k = f_k | A_k\} P\{\seq{y} \in \mathcal{C}_{f_k}\} 1\{\hat{\seq{y}} - \seq{y} \in f_k(\mathcal{X}^{n_k})\}.
\end{IEEEeqnarray*}
This together with \eqref{eq:OriginalDefinitionX2OfAsympGoodLCC} gives
$$
\biggl| \frac{1}{m_k} \ln \frac{P\{\seq{y} \in \mathcal{C}_{F_k}, \hat{\seq{y}} \in \mathcal{C}_{F_k} | A_k\}}{P\{\hat{\seq{y}} - \seq{y} \in F_k(\mathcal{X}^{n_k}) | A_k\}} + \ln |\mathcal{Y}| - R_c(\seqx{F}) \biggr| \le \epsilon.
$$
Then the condition \eqref{eq:OriginalDefinitionOfAsympGoodLCC} can be rewritten as
\begin{IEEEeqnarray}{l}
\max_{\seq{y}: \seq{y} \ne 0^{m_k}} \frac{1}{m_k} \ln P\{\seq{y} \in F_k(\mathcal{X}^{n_k}) | A_k\} \IEEEnonumber \\
\qquad \le -\ln|\mathcal{Y}| + R_c(\seqx{F}) + \delta + \epsilon \label{eq:OriginalDefinition2OfAsympGoodLCC}
\end{IEEEeqnarray}
by noting that $\epsilon$ is arbitrary.

According to \cite{JSCC:Yang200904}, a sequence $\seqx{F}$ of random linear codes is said to be $\delta$-asymptotically good for lossless JSCC if it satisfies
\begin{IEEEeqnarray}{l}
\limsup_{k \to \infty} \max_{\scriptstyle \seq{x}, \hat{\seq{x}}: \seq{x} \ne \hat{\seq{x}} \atop \scriptstyle \seq{y}, \hat{\seq{y}}} \IEEEnonumber \\
\quad \frac{1}{n_k} \ln \left( \frac{P\{\mathcal{F}_{F_k}(\seq{x}) = \seq{y}, \mathcal{F}_{F_k}(\hat{\seq{x}}) = \hat{\seq{y}}\}}{P\{\mathcal{F}_{F_k}(\seq{x}) = \seq{y}\} P\{\mathcal{F}_{F_k}(\hat{\seq{x}}) = \hat{\seq{y}}\}} \right) \le \delta. \label{eq:OriginalDefinitionOfAsympGoodLSCC}
\end{IEEEeqnarray}
where $\mathcal{F}_{F_k}(\seq{x}) \eqdef F_k(\seq{x}) + \bar{Y}^{m_k}$ and $\bar{Y}^{m_k}$ is an independent uniform random vector on $\mathcal{Y}^{m_k}$. By the arguments in the proof (in \cite{JSCC:Yang200904}) of Proposition~\ref{pr:IndependenceLC1}, we obtain an alternative condition:
\begin{equation}\label{eq:OriginalDefinition2OfAsympGoodLSCC}
\limsup_{k \to \infty} \max_{\scriptstyle \seq{x}: \seq{x} \ne 0 \atop \scriptstyle \seq{y}} \frac{1}{n_k} \ln \left( |\mathcal{Y}|^{m_k} P\{F_k(\seq{x}) = \seq{y}\} \right) \le \delta.
\end{equation}

The requirements given above are fundamental, but are not easy and convenient for use. The next three propositions show that spectra of linear codes can serve as alternative criteria of good linear codes, and that the uniform random permutation is a useful tool for constructing good linear codes.

\begin{proposition}\label{pr:KernelSpectrumCondition}
Let $\seqx{F}$ be a sequence of random linear codes with the asymptotic source transmission rate $R_s(\seqx{F})$. If it satisfies the \emph{kernel-spectrum condition}:
\begin{equation}\label{eq:DefinitionOfAsympGoodLSC}
\limsup_{k \to \infty} \max_{P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}} \frac{1}{n_k} \ln \alpha(\ker F_k)(P) \le \delta
\end{equation}
then the sequence of random linear codes $\rtilde{F}_k = F_k \circ \Sigma_{n_k}$ is $\delta$-asymptotically good for lossless source coding.
\end{proposition}

\begin{proposition}\label{pr:ImageSpectrumCondition}
Let $\seqx{F}$ be a sequence of random linear codes with the asymptotic channel transmission rate $R_c(\seqx{F})$. If it satisfies the \emph{image-spectrum condition}:
\begin{equation}\label{eq:DefinitionOfAsympGoodLCC}
\limsup_{k \to \infty} \max_{Q \in \mathcal{P}_{m_k}(\mathcal{Y}) \backslash \{P_{0^{m_k}}\}} \frac{1}{m_k} \ln \alpha(F_k(\mathcal{X}^{n_k}))(Q) \le \delta
\end{equation}
then the sequence of linear codes $\Sigma_{m_k} \circ F_k$ is $\delta$-asymptotically good for channel coding.
\end{proposition}

\begin{proposition}\label{pr:JointSpectrumCondition}
Let $\seqx{F}$ be a sequence of random linear codes. If it satisfies the \emph{joint-spectrum condition}:
\begin{equation}\label{eq:DefinitionOfAsympGoodLSCC}
\limsup_{k \to \infty} \max_{\scriptstyle P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}, \atop \scriptstyle Q \in \mathcal{P}_{m_k}(\mathcal{Y})} \frac{1}{n_k} \ln \alpha(F_k)(P, Q) \le \delta
\end{equation}
then the sequence of linear codes $\tilde{F}_k = \Sigma_{m_k} \circ F_k \circ \Sigma_{n_k}$ is $\delta$-asymptotically good for lossless JSCC.
\end{proposition}

For convenience, we define the function
\begin{equation}\label{eq:DefinitionOfRho}
\rho(F) \eqdef \max_{\scriptstyle P \in \mathcal{P}_n(\mathcal{X}) \backslash \{P_{0^n}\}, \atop \scriptstyle Q \in \mathcal{P}_{m}(\mathcal{Y})} \frac{1}{n} \ln \alpha(F)(P, Q)
\end{equation}
for any random linear code $F: \mathcal{X}^n \to \mathcal{Y}^{m}$. Then the condition \eqref{eq:DefinitionOfAsympGoodLSCC} can be written as $\limsup_{k \to \infty} \rho(F_k) \le \delta$.

As shown above, as long as the linear codes satisfy the code-spectrum requirements, we can then construct good ensembles of random linear codes by random permutations. So from now on, we shall use the conditions \eqref{eq:DefinitionOfAsympGoodLSC}, \eqref{eq:DefinitionOfAsympGoodLCC}, and \eqref{eq:DefinitionOfAsympGoodLSCC} as the formal definitions of $\delta$-asymptotically good (random) linear codes for lossless source coding, channel coding, and lossless JSCC, respectively. These linear codes are then called $\delta$-asymptotically good \emph{linear source codes} (LSCs), $\delta$-asymptotically good \emph{linear channel codes} (LCCs), and $\delta$-asymptotically good \emph{linear source-channel codes} (LSCCs), respectively. Alternatively, they are said to be $\delta$-asymptotically SC-good, $\delta$-asymptotically CC-good, and $\delta$-asymptotically SCC-good, respectively. When $\delta = 0$, we use the simplified term ``asymptotically good''; when talking about $\delta$-asymptotically good LSCs (resp., LCCs), we tacitly assume that their source (resp., channel) transmission rates converge in probability. Since the conditions of $\delta$-asymptotically good LSCs or LCCs are only concerned with the kernel or image of linear codes, we also introduce the concepts of equivalence in the sense of LSCs or LCCs. For any linear codes $f: \mathcal{X}^n \to \mathcal{Y}^m$ and $g: \mathcal{X}^n \to \mathcal{Y}^m$, they are said to be \emph{SC-equivalent} if they have the same kernel, and they are said to be \emph{CC-equivalent} if they have the same image.

The following propositions investigate the relations among $\delta$-asymptotically good LSCs, LCCs, and LSCCs.

\begin{proposition}\label{pr:RelationBetweenLSCandLCC}
For a sequence $\seqx{F}$ of $\delta$-asymptotically good LSCs, there exists a sequence $\seqx{G} = \{G_k\}_{k=1}^\infty$ of $\delta$-asymptotically good LCCs $G_k: \mathcal{X}^{l_k} \to \mathcal{X}^{n_k}$ such that $G_k(\mathcal{X}^{l_k}) = \ker F_k$ for all $k \in \pintegers$.
\end{proposition}

\begin{proposition}\label{pr:RelationBetweenLCCandLSC}
For a sequence $\seqx{F}$ of $\delta$-asymptotically good LCCs, there exists a sequence $\seqx{G} = \{G_k\}_{k=1}^\infty$ of $\delta$-asymptotically good LSCs $G_k: \mathcal{Y}^{m_k} \to \mathcal{Y}^{l_k}$ such that $\ker G_k = F_k(\mathcal{X}^{n_k})$ for all $k \in \pintegers$.
\end{proposition}

\begin{proposition}\label{pr:RelationBetweenLSCCandLSCLCC}
Let $\seqx{F}$ be a sequence of $\delta$-asymptotically good LSCCs. Then it is $\delta$-asymptotically SC-good whenever its source transmission rate converges in probability, and it is $\delta\overline{R}(\seqx{F})$-asymptotically CC-good whenever its channel transmission rate converges in probability.
\end{proposition}

By Propositions~\ref{pr:RelationBetweenLSCandLCC}, \ref{pr:RelationBetweenLCCandLSC}, and \ref{pr:RelationBetweenLSCCandLSCLCC}, we thus establish the relations among different kinds of good linear codes. These relations are all depicted in Fig.~\ref{fig:Relation1}.
\begin{figure}[h]
$$
\begin{array}{rcl}
&\mbox{good LSCCs} \\
\swarrow & &\searrow \\
\mbox{good LSCs} &\Longleftrightarrow &\mbox{good LCCs} \\
\end{array}
$$
\caption{The relations among different kinds of good linear codes}\label{fig:Relation1}
\end{figure}
Among these relations, the relations (Proposition~\ref{pr:RelationBetweenLSCCandLSCLCC}) that good LSCCs are good LSCs and LCCs deserve much more attention. This fact indicates the fundamental role of good LSCCs, and allows us to only concentrate on one problem, namely, the construction of linear codes with good joint spectra. So in the following sections, we shall investigate this problem in depth. Also note that, however, there are two arrows missing in Fig.~\ref{fig:Relation1}, one from LSC to LSCC and the other from LCC to LSCC. Then naturally, we have such a question: are $\delta$-asymptotically good LSCs (resp., LCCs) $\delta$-asymptotically SCC-good, or can we construct $\delta$-asymptotically good LSCCs which are SC-equivalent (resp., CC-equivalent) to given $\delta$-asymptotically good LSCs (resp., LCCs)?

As $\delta$ is close to zero, it is clear that $\delta$-asymptotically good LSCs (or LCCs) may not be $\delta$-asymptotically SCC-good. \cite[Theorem 4]{JSCC:Yang200503} shows that there exist asymptotically good LSCs in the ensemble of low-density parity-check matrices. However, \cite[Corollary~4.2]{JSCC:Yang200904} proves that these codes are not asymptotically SCC-good because the matrices are sparse. It is well known that, for any linear code over a finite field, there exits a CC-equivalent systematic linear code. According to \cite[Corollary~4.1]{JSCC:Yang200904}, high rate systematic linear codes are not asymptotically SCC-good. So we can always find asymptotically good systematic LCCs which are not asymptotically SCC-good.

Now, the remaining question is if and how we can construct $\delta$-asymptotically good LSCCs which are SC-equivalent (resp., CC-equivalent) to given $\delta$-asymptotically good LSCs (resp., LCCs). The answer is positive and will be given in Section~\ref{sec:GeneralPrinciplesForConstructingGoodLSCC}.

We close this section with a simple proposition.

\begin{proposition}\label{pr:DiagonalArgument}
Let $\{\seqx{F}_i = \{F_{i,k}\}_{k=1}^\infty\}_{i=1}^\infty$ be a family of sequences of random linear codes $F_{i,k}: \mathcal{X}^{n_k} \to \mathcal{Y}^{m_k}$. The sequence $\seqx{F}_i$ ($i \in \pintegers$) is $\delta_i$-asymptotically SCC-good where $\delta_i$ is nonincreasing in $i$ and converges to $\delta$ as $i \to \infty$. Define the random linear code $G_{i,k} \eqdef F_{i_0,k}$ where
$$
i_0 \eqdef \arg \min_{1 \le j \le i} \rho(F_{j,k}).
$$
Then $\{G_{k,k}\}_{k=1}^\infty$ is $\delta$-asymptotically SCC-good.
\end{proposition}

The proofs of this section are given in Section~\ref{subsec:ProofOfConceptsOfGoodLinearCodes}.



\section{General Principles for Constructing Good Linear Source-Channel Codes}\label{sec:GeneralPrinciplesForConstructingGoodLSCC}


\subsection{A Class of SCC-Good Codes Derived from Certain Maximum-Rank-Distance Codes}\label{subsec:MRDLSCC}

Recall that in \cite[Sec.~III]{JSCC:Yang200904}, a random linear code $F: \mathcal{X}^n \to \mathcal{Y}^m$ is said to be good for JSCC if it satisfies
\begin{equation}\label{eq:SuperGoodLinearCodes1}
\alpha(F)(P, Q) = 1
\end{equation}
for all $P \in \mathcal{P}_n(\mathcal{X}) \backslash \{P_{0^n}\}$ and all $Q \in \mathcal{P}_m(\mathcal{Y})$. To distinguish good linear codes for JSCC from good linear codes in other contexts, we say that $F$ is SCC-good. It is clear that SCC-good linear codes are asymptotically SCC-good. By Proposition~\ref{pr:SpectrumPropertyOfFunctions}, we also have an alterative condition:
\begin{equation}\label{eq:SuperGoodLinearCodes2}
P\{\tilde{F}(\seq{x}) = \seq{y}\} = |\mathcal{Y}|^{-m} \quad \forall \seq{x} \in \mathcal{X}^n \backslash \{0^n\}, \forall \seq{y} \in \mathcal{Y}^m.
\end{equation}

The random linear code $\rlccode{q,n,m}$ (defined in Proposition~\ref{pr:GoodLinearCodes}) is obviously SCC-good (cf. \eqref{eq:Identity1OfGLC}, \eqref{eq:Identity2OfGLC}) but in some sense trivial, since its distribution has support $\field{q}^{n \times m}$, the set of all linear codes $f:\field{q}^n\to\field{q}^m$. In this subsection we provide further examples of SCC-good random linear codes with support size much smaller than $|\field{q}^{n\times m}|=q^{mn}$. These are derived from so-called maximum-rank-distance (MRD) codes, and have the stronger property
\begin{equation}\label{eq:SuperGoodBeforeSymmLinearCodes}
  P\{F(\seq{x}) = \seq{y}\} = |\mathcal{Y}|^{-m} \quad \forall \seq{x} \in \mathcal{X}^n \backslash \{0^n\}, \forall \seq{y} \in \mathcal{Y}^m
\end{equation}
which one might call ``SCC-good before symmetrization''.

Next we give a brief review of MRD codes. Let $n,m,k$ be positive integers with $k\leq\min\{n,m\}$. Write $n'=\max\{n,m\}$, $m'=\min\{n,m\}$ (so that $(n',m')$ equals either $(n,m)$ or $(m,n)$). An \emph{$(n,m,k)$ maximum-rank-distance (MRD) code} over $\field{q}$ is a set $\mathcal{C}$ of $q^{kn'}$ matrices in $\field{q}^{n\times m}$ such that 
  \begin{equation}
    \label{eq:MRD}
    \rank{\mat{A}-\mat{B}}\geq m'-k+1\text{ for all distinct }
    \mat{A},\mat{B}\in\mathcal{C}.
  \end{equation}
MRD codes are optimal for the rank distance $\rdist: (\mat{A},\mat{B}) \mapsto \rank{\mat{A}-\mat{B}}$ on $\field{q}^{n\times m}$ in the same way as maximum distance separable (MDS) codes are optimal for the Hamming distance, as the following reasoning shows: Let $\mathcal{C}\subseteq\field{q}^{n\times m}$ have minimum rank distance $d$, $1\leq d\leq m'$. We may view $\mathcal{C}$ as a code of length $m$ over $\field{q}^n$ (the columns of $\mat{A}\in\field{q}^{n\times m}$ being the ``entries'' of $\mat{A}$). As such $\mathcal{C}$ has Hamming distance $\geq d$ (since a matrix of rank $d$ must have at least $d$ nonzero columns). Hence $|\mathcal{C}|\leq q^{n(m-d+1)}$ by the Singleton bound. By transposing we also have $|\mathcal{C}|\leq q^{m(n-d+1)}$, so that
  \begin{equation}
    \label{eq:MRDsingleton}
    |\mathcal{C}|\leq\min\left\{q^{n(m-d+1)},q^{m(n-d+1)}\right\}=q^{n'(m'-d+1)}.
  \end{equation}
The codes for which \eqref{eq:MRDsingleton} is sharp are exactly the $(n,m,k)$ MRD codes with $k=m'-d+1$.

MRD codes were introduced in \cite{JSCC:Delsarte197800} under the name ``Singleton system'' and investigated further in \cite{JSCC:Gabidulin198501,JSCC:Roth199103}. As shown in \cite{JSCC:Delsarte197800,JSCC:Gabidulin198501}, linear $(n,m,k)$ MRD codes over $\field{q}$ (i.e.\ MRD codes which are $\field{q}$-subspaces of $\field{q}^{n\times m}$) exist for all $n,m,k$ with $1\leq k\leq\min\{n,m\}$. The standard construction uses $q$-analogues of Reed-Solomon codes, which are defined as follows: Assuming $n\geq m$ for a moment, let $x_1,\dots,x_m\in\field{q^n}$ be linearly independent over $\field{q}$. For $1\leq k\leq m$ let $D_k$ be the linear $[m,k]$ code over $\field{q^n}$ having generator matrix
\begin{equation}
  \label{eq:qRS}
  \mat{G}_k=
  \begin{pmatrix}
    x_1&x_2&\hdots&x_m\\
    x_1^q&x_2^q&\hdots&x_m^q\\
    \vdots&\vdots&&\vdots\\
    x_1^{q^{k-1}}&x_2^{q^{k-1}}&\hdots&x_m^{q^{k-1}}
  \end{pmatrix}.
\end{equation}
Replace each codeword $\seq{c}=(c_1,\dots,c_m)\in D_k$ by the $n \times m$ matrix $\mat{C}$ having as columns the coordinate vectors of $c_j$ with respect to some fixed basis of $\field{q^n}$ over $\field{q}$. The set $\mathcal{C}_k$ of $q^{nk}=|D_k|$ matrices $\mat{C}$ obtained in this way forms a linear $(n,m,k)$ MRD code over $\field{q}$. The restriction $n\geq m$ is not essential, since transposing each matrix of an $(n,m,k)$ MRD code yields an $(m,n,k)$ MRD code. We shall follow \cite{JSCC:Silva200809} and call the codes $\mathcal{C}_k\subseteq\field{q}^{n \times m}$ ($1\leq k\leq m\leq n$), as well as their transposes, \emph{Gabidulin codes}. Thus linear $(n,m,k)$ MRD codes over $\field{q}$ exist for all positive integers $n,m,k$ with $k\leq\min\{n,m\}$.

For our construction of SCC-good random linear codes we need the following property of Gabidulin codes.

\begin{proposition}\label{pr:MRDLSCC}
Suppose $\mathcal{C}\subseteq\field{q}^{n\times m}$ is a Gabidulin code. Then $\{\seq{x}\mat{A};\mat{A}\in\mathcal{C}\}=\field{q}^m$ for every $\seq{x} \in \field{q}^n \setminus \{0^n\}$, and similarly $\{\mat{A}\seq{y}^T;\mat{A}\in\mathcal{C}\}=\field{q}^n$ for every $\seq{y} \in \field{q}^m \setminus \{0^m\}$.
\end{proposition}

\begin{theorem}\label{th:MRDLSCC}
Let $\mathcal{C}\subseteq\field{q}^{n\times m}$ be a Gabidulin code. Define a random linear code $F:\field{q}^n\to\field{q}^m$ by
\begin{equation*}
  P\{F=\mat{A}\}=
  \begin{cases}
    \frac{1}{|\mathcal{C}|}&\text{if $\mat{A}\in\mathcal{C}$},\\
    0&\text{otherwise}.
  \end{cases}
\end{equation*}
Then $F$ is SCC-good.
\end{theorem}

Theorem~\ref{th:MRDLSCC} provides us with SCC-good random linear codes $F:\field{q}^n\to\field{q}^m$ of support size as small as $q^{n'}=q^{\max\{n,m\}}$, realized by an $(n,m,1)$ MRD code, which has minimum rank distance $d = m' = \min\{n,m\}$ (the full-rank case). In fact, we showed in \cite{JSCC:Yang201008} that $q^{\max\{n,m\}}$ is the minimum support size of an SCC-good random linear code satisfying the stronger condition \eqref{eq:SuperGoodBeforeSymmLinearCodes}, and that a random linear code of support size $q^{\max\{n,m\}}$ is SCC-good before symmetrization if and only if it is uniformly distributed over an $(n,m,1)$ MRD code.

As an application of Theorem~\ref{th:MRDLSCC}, the next example gives us some insights into the general form of a random linear code that is SCC-good before symmetrization.

\begin{example}
Let $m=n=q=2$ and $\field{4} = \field{2}[\alpha]$ with $\alpha^2 = \alpha+1$. It is clear that $\{1, \alpha\}$ is a basis of $\field{4}$. By definition of Gabidulin codes, we may consider the generator matrix $\mat{G}_1 = (1\;\; \alpha)$. Then the Gabidulin code $\mathcal{C}_1$ is
\[
\left\{(0\;\; 0), (1\;\; \alpha), (\alpha\;\; 1+\alpha), (1+\alpha\;\; 1)\right\}
\]
or
\[
\left\{
\begin{pmatrix} 0 &0\\ 0 &0\end{pmatrix},
\begin{pmatrix} 1 &0\\ 0 &1\end{pmatrix},
\begin{pmatrix} 0 &1\\ 1 &1\end{pmatrix},
\begin{pmatrix} 1 &1\\ 1 &0\end{pmatrix}\right\}.
\]
Note that $\mathcal{C}_1$ is isomorphic to $\field{4}$. By Theorem~\ref{th:MRDLSCC}, the random linear code uniformly distributed over $\mathcal{C}_1$, which we also denote by $\mathcal{C}_1$, is SCC-good. Interchanging the columns of each matrix in $\mathcal{C}_1$ gives another SCC-good random linear code
\[
\mathcal{C}_2 = \left\{
\begin{pmatrix} 0 &0\\ 0 &0\end{pmatrix},
\begin{pmatrix} 0 &1\\ 1 &0\end{pmatrix},
\begin{pmatrix} 1 &1\\ 0 &1\end{pmatrix},
\begin{pmatrix} 1 &0\\ 1 &1\end{pmatrix}\right\}.
\]
The cosets of $\mathcal{C}_1$, such as
\[
\mathcal{C}_3 = \left\{
\begin{pmatrix} 0 &1\\ 0 &0\end{pmatrix},
\begin{pmatrix} 1 &1\\ 0 &1\end{pmatrix},
\begin{pmatrix} 0 &0\\ 1 &1\end{pmatrix},
\begin{pmatrix} 1 &0\\ 1 &0\end{pmatrix}\right\}
\]
are also SCC-good. Note that $\mathcal{C}_3$ contains only one matrix of full rank. Finally, let $\mathcal{C} \eqdef \mathcal{C}_I$, where $I$ is an arbitrary random variable taking values in $\mathcal{I}_3$. It is clear that $\mathcal{C}$ is SCC-good.
\end{example}

The proofs of this subsection are given in Section~\ref{subsec:ProofOfMRDLSCC}.


\subsection{Constructing Good LSCCs Based on Good LSCs or LCCs}\label{subsec:ConstructingGoodLSCCGPA}

The condition \eqref{eq:SuperGoodLinearCodes2} is a very strong condition, which in fact reflects the property of the alphabet. Therefore, combined with the injective property of mappings, we say that an alphabet (an abelian group) $\mathcal{X}$ is \emph{super good} if there exists a sequence $\{F_n\}_{n=1}^\infty$ of independent SCC-good random linear codes $F_n: \mathcal{X}^n \to \mathcal{X}^n$ such that
\begin{equation}\label{eq:InjectiveProbabilityCondition}
\inf_{n \in \pintegers} P\{|\ker F_n| = 1\} > 0.
\end{equation}
We denote by $\{\sgcode{\mathcal{X},n}\}_{n=1}^\infty$ the sequence of such SCC-good random linear codes. Then, a natural question is what abelian groups are super good.

Recall that $\mathcal{X}$ is said to be \emph{elementary abelian} if $\mathcal{X}$ is isomorphic to $\integers_p^s$ for some prime $p$ and some integer $s\geq 0$. The nontrivial elementary abelian $p$-groups are exactly the additive groups of the finite fields $\field{q}$ with $q=p^r$.

From Proposition~\ref{pr:GoodLinearCodes} and a well-known result (Theorem~\ref{th:RankOfRLC}), it follows that all elementary abelian groups are super good.

\begin{theorem}[see \cite{JSCC:Cooper200010}]\label{th:RankOfRLC}
Let $\rank{f}$ denote the rank of the generator matrix of the linear code $f: \field{q}^n \to \field{q}^m$. Then
\begin{equation}\label{eq:RankOfRLC3}
P\left\{\rank{\rlccode{q,n,n}} = n\right\} = \prod_{i=1}^n (1-q^{-i}) > K_q
\end{equation}
where $K_q \eqdef \prod_{i=1}^\infty (1-q^{-i})$ can be expanded as an alternating series
\[
1+\sum_{k=1}^\infty (-1)^k\left[q^{-\frac{3k(k-1)}{2}}+q^{-\frac{3k(k+1)}{2}}\right]
\]
by Euler's pentagonal number theorem (see \cite{JSCC:Andrews198311}).
\end{theorem}

The next theorem shows that, conversely, a super good finite abelian group is necessarily elementary abelian.

\begin{theorem}\label{th:elementary_abelian}
For nontrivial abelian groups $\mathcal{X}$ and $\mathcal{Y}$, if there exists an SCC-good random linear code $F: \mathcal{X}^n\to\mathcal{Y}^m$, then $\mathcal{X}$ and $\mathcal{Y}$ are elementary abelian $p$-groups for the same prime $p$ (provided that $m,n\geq 1$).
\end{theorem}

Now let us investigate the relation between conditions \eqref{eq:SuperGoodLinearCodes2} and \eqref{eq:InjectiveProbabilityCondition} for elementary abelian groups.

\begin{theorem}\label{th:KernelOfSuperGoodLinearCodes}
Let $\mathcal{X}$ be an elementary abelian group of order $q=p^r$. Then for every SCC-good random linear code $F:\mathcal{X}^n \to \mathcal{X}^n $ the following bound holds:
\begin{equation*}
P\{|\ker F| = 1\} \geq \frac{p-2+q^{-n}}{p-1}.
\end{equation*}
\end{theorem}

From Theorem~\ref{th:KernelOfSuperGoodLinearCodes}, an immediate consequence follows.

\begin{corollary}\label{co:KernelOfSuperGoodLinearCodes}
Let $\mathcal{X}$ be an elementary abelian $p$-group for some prime $p>2$. Then there exists a positive constant $c(|\mathcal{X}|)$ (which may be taken as $c(|\mathcal{X}|)= 1-\frac{1}{p-1}$) such that $P\{|\ker F|=1\}\geq c(|\mathcal{X}|)$ for every SCC-good random linear code $F: \mathcal{X}^n \to \mathcal{X}^n$.
\end{corollary}

However, the conclusion of Corollary~\ref{co:KernelOfSuperGoodLinearCodes} does not hold for $p=2$.

\begin{proposition}\label{pr:KernelOfSuperGoodLinearCodes}
If $\mathcal{X}$ is an elementary abelian $2$-group, there exists a sequence $\{F_n\}_{n=1}^\infty$ of SCC-good random linear codes $F_n:\mathcal{X}^n\to\mathcal{X}^n$ such that $\lim_{n\to\infty} P\{|\ker F_n|=1\}=0$.
\end{proposition}

With the preparation above, let us investigate the problem of how to construct $\delta$-asymptotically good LSCCs which are SC-equivalent (resp., CC-equivalent) to given $\delta$-asymptotically good LSCs (resp., LCCs).

The next theorem gives some ways for constructing SC-equivalent or CC-equivalent linear codes.

\begin{theorem}\label{th:ConstructionOfEquivalentCodes}
Let $F: \mathcal{X}^n \to \mathcal{Y}^m$ be a random linear code. If $\mathcal{Y}$ is an elementary abelian group of size $q$, then the random linear code $G_1 \eqdef \rlccode{q,m,m} \circ F \eqvar{d} \rlccode{q,m,m} \circ \Sigma_m \circ F$ satisfies
\begin{IEEEeqnarray}{l}
P\{\ker G_1 = \ker F\} > K_q \label{eq:SCEquivalentProbability} \\
E[S_{\mathcal{Y}|\mathcal{X}}(G_1)(Q|P)] \IEEEnonumber \\
\qquad \le S_{\mathcal{Y}}(\mathcal{Y}^m)(Q) + 1\{Q = P_{0^{m}}\} E[S_{\mathcal{Y}|\mathcal{X}}(F)(P_{0^{m}}|P)] \IEEEnonumber \\
\hspace{7em} \forall P \in \mathcal{P}_n(\mathcal{X}) \backslash \{P_{0^n}\}, Q \in \mathcal{P}_m(\mathcal{Y}). \label{eq:SCEquivalentCodeSpectrum}
\end{IEEEeqnarray}
If $\mathcal{X}$ is an elementary abelian group of size $q$, then the random linear code $G_2 \eqdef F \circ \rlccode{q,n,n} \eqvar{d} F \circ \Sigma_n \circ \rlccode{q,n,n}$ satisfies
\begin{IEEEeqnarray}{l}
P\{G_2(\mathcal{X}^n) = F(\mathcal{X}^n)\} > K_q \label{eq:CCEquivalentProbability} \\
E[S_{\mathcal{Y}|\mathcal{X}}(G_2)(Q|P)] = E[S_{\mathcal{Y}}(F(\mathcal{X}^n))(Q)] \IEEEnonumber \\
\hspace{5em} \forall P \in \mathcal{P}_n(\mathcal{X}) \backslash \{P_{0^n}\}, Q \in \mathcal{P}_m(\mathcal{Y}). \label{eq:CCEquivalentCodeSpectrum}
\end{IEEEeqnarray}
\end{theorem}

Based on Theorem~\ref{th:ConstructionOfEquivalentCodes}, we thus find the answer of the problem by the following theorem.

\begin{theorem}\label{th:ConstructionOfGoodEquivalentCodes}
Let $\seqx{f} = \{f_k\}_{k=1}^\infty$ be a sequence of linear codes $f_k: \mathcal{X}^{n_k} \to \mathcal{Y}^{m_k}$. If $\seqx{f}$ is a sequence of $\delta$-asymptotically good LSCs satisfying
\begin{equation}\label{eq:ConstructionOfGoodEquivalentCodes}
R_c(\seqx{f}) = \ln |\mathcal{Y}|
\end{equation}
and $\mathcal{Y}$ is elementary abelian, then there exists a sequence $\{g_{1,k}\}_{k=1}^\infty$ of $\delta$-asymptotically good LSCCs $g_{1,k}: \mathcal{X}^{n_k} \to \mathcal{Y}^{m_k}$ such that $g_{1,k}$ is SC-equivalent to $f_k$ for each $k \in \pintegers$. Analogously, if $\seqx{f}$ is a sequence of $\delta$-asymptotically good injective LCCs and $\mathcal{X}$ is elementary abelian, then there exists a sequence $\{g_{2,k}\}_{k=1}^\infty$ of $\delta/R(\seqx{f})$-asymptotically good injective LSCCs $g_{2,k}: \mathcal{X}^{n_k} \to \mathcal{Y}^{m_k}$ such that $g_{2,k}$ is CC-equivalent to $f_k$ for each $k \in \pintegers$.
\end{theorem}

Theorem~\ref{th:ConstructionOfGoodEquivalentCodes} is a very fundamental result, which not only claims the existence of SC-equivalent (or CC-equivalent) $\delta$-asymptotically good LSCCs but also gives the way for constructing such good LSCCs by concatenating rate-$1$ linear codes. Recalling that rate-$1$ linear codes (e.g., the ''accumulate'' code) are frequently used to construct good LCCs (e.g., \cite{JSCC:Divsalar199809,JSCC:Pfister200306,JSCC:Abbasfar200704}), we believe that finding good rate-$1$ LSCCs is an issue deserving further consideration.

The proofs of Theorem~\ref{th:RankOfRLC} and Corollary~\ref{co:KernelOfSuperGoodLinearCodes} are omitted, while the proofs of the other results are given in Section~\ref{subsec:ProofOfConstructingGoodLSCCGPA}.


\subsection{A General Scheme for Constructing Good LSCCs}\label{subsec:ConstructingGoodLSCCGPB}

Theorems~\ref{th:MRDLSCC} and \ref{th:ConstructionOfGoodEquivalentCodes} do give possible ways for constructing asymptotically good LSCCs. However, such constructions are somewhat difficult to implement in practice, because the generator matrices of a Gabidulin code or $\rlccode{q,n,n}$ are not sparse. Thus, our next question is how to construct $\delta$-asymptotically good LSCCs based on sparse matrices so that known iterative decoding procedures have low complexity. For such purposes, in this subsection, we shall present a general scheme for constructing $\delta$-asymptotically good LSCCs.

Let $\seqx{F} = \{F_k\}_{k=1}^\infty$ be a sequence of random linear codes $F_k: \mathcal{X}^{n_k} \to \mathcal{Y}^{m_k}$. We say that $\seqx{F}$ is $\delta$-asymptotically SCC-good relative to the sequence $\{A_k\}_{k=1}^\infty$ of subsets $A_k \subseteq \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}$ if
$$
\limsup_{k \to \infty} \max_{P \in A_k, Q \in \mathcal{P}_{m_k}(\mathcal{Y})} \frac{1}{n_k} \ln \alpha(F_k)(P, Q) \le \delta.
$$
Clearly, this is a generalization of $\delta$-asymptotically good LSCCs, and may be regarded as an approximate version of $\delta$-asymptotically good LSCCs especially when $A_k$ is a proper subset of $\mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}$. The next theorem shows that $\delta$-asymptotically good LSCCs may be constructed based on these linear codes by serial concatenations.

\begin{theorem}\label{th:ConstructionOfGoodLSCC}
Let $\{G_k\}_{k=1}^\infty$ be a sequence of random linear codes $G_k: \mathcal{Y}^{m_k} \to \mathcal{Z}^{l_k}$ that is $\delta$-asymptotically SCC-good relative to the sequence $\{A_k\}_{k=1}^\infty$ of sets $A_k \subseteq \mathcal{P}_{m_k}(\mathcal{Y}) \backslash \{P_{0^{m_k}}\}$. If there is a sequence $\seqx{F} = \{F_k\}_{k=1}^\infty$ of random linear codes $F_k: \mathcal{X}^{n_k} \to \mathcal{Y}^{m_k}$ such that
\begin{equation}\label{eq:ConstructionOfGoodLSCC1}
F_k(\mathcal{X}^{n_k} \backslash \{0^{n_k}\}) \subseteq \bigcup_{P \in A_k} \mathcal{T}_{P}^{m_k}(\mathcal{Y})
\end{equation}
then we have
$$
\limsup_{k \to \infty} \rho(G_k \circ \Sigma_{m_k} \circ F_k) \le \frac{\delta}{\underline{R}(\seqx{F})}.
$$
\end{theorem}

\begin{remark}\label{re:ConstructionOfGoodLSCC}
Take, for example,
\begin{equation}\label{eq:ApproximateGoodSet}
A_k = \{P \in \mathcal{P}_{m_k}(\mathcal{Y}) | P(0) \in [0, 1-\gamma]\}
\end{equation}
for some $\gamma\in(0,1)$. Then Theorem~\ref{th:ConstructionOfGoodLSCC} shows that we can construct asymptotically good LSCCs by a serial concatenation scheme, where the inner code is approximately $\delta$-asymptotically SCC-good and the outer code has good distance properties. As we know (see \cite{JSCC:Gallager196300, JSCC:Bennatan200403, JSCC:Como2008, JSCC:Yang201004}, etc.), there exist good LDPC codes over finite fields such that \eqref{eq:ConstructionOfGoodLSCC1} is met for an appropriate $\gamma$, so the problem to be solved is to find a sequence of linear codes that is $\delta$-asymptotically good relative to a sequence of sets such as \eqref{eq:ApproximateGoodSet}. In the next section, we shall find such candidates in a family of codes called LDGM codes.
\end{remark}

More interestingly, since an injective linear code $F_k$ always satisfies the condition \eqref{eq:ConstructionOfGoodLSCC1} with $A_k = \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}$, we immediately obtain a corollary from Theorem~\ref{th:ConstructionOfGoodLSCC}.

\begin{corollary}\label{co:ConstructionOfGoodLSCCbyInjectiveMapping}
Let $\{G_k\}_{k=1}^\infty$ be a sequence of $\delta$-asymptotically good random LSCCs $G_k: \mathcal{Y}^{m_k} \to \mathcal{Z}^{l_k}$. Let $\seqx{F} = \{F_k\}_{k=1}^\infty$ be a sequence of injective random linear codes $F_k: \mathcal{X}^{n_k} \to \mathcal{Y}^{m_k}$. Then
$$
\limsup_{k \to \infty} \rho(G_k \circ \Sigma_{m_k} \circ F_k) \le \frac{\delta}{\underline{R}(\seqx{F})}.
$$
\end{corollary}

Analogously, we have the following proposition.

\begin{proposition}\label{pr:ConstructionOfGoodLSCCbySurjectiveMapping}
Let $\{F_k\}_{k=1}^\infty$ be a sequence of $\delta$-asymptotically good random LSCCs $F_k: \mathcal{X}^{n_k} \to \mathcal{Y}^{m_k}$. Let $\{G_k\}_{k=1}^\infty$ be a sequence of surjective random linear codes $G_k: \mathcal{Y}^{m_k} \to \mathcal{Z}^{l_k}$. Then
$$
\limsup_{k \to \infty} \rho(G_k \circ \Sigma_{m_k} \circ F_k) \le \delta.
$$
\end{proposition}

The above two results tell us that, any linear code, if serially concatenated with an outer injective linear code or an inner surjective linear code, will not have worse performance in terms of the condition \eqref{eq:DefinitionOfAsympGoodLSCC}. Maybe, if we are lucky, some linear codes with better joint spectra can be constructed in this way. Note that a nonsingular rate-$1$ linear code is both injective and surjective, so adding rate-$1$ linear codes into a serial concatenation scheme is always a not-bad idea for constructing good LSCCs. Certainly, the addition of rate-$1$ codes may have a negative impact on the decoding performance.

The proof of Corollary~\ref{co:ConstructionOfGoodLSCCbyInjectiveMapping} is omitted, while the proofs of the other results are given in Section~\ref{subsec:ProofOfConstructingGoodLSCCGPB}.


\section{An Explicit Construction Based on Sparse Matrices}\label{sec:ExplicitConstruction}

In light of Remark~\ref{re:ConstructionOfGoodLSCC}, we proceed to investigate the joint spectra of regular low-density genrator matrix (LDGM) codes over finite fields. In this section (except Proposition~\ref{pr:SingleCodeSpectrum}), we only deal with codes over a finite field $\field{q}$, so for convenience, we omit all subscripts of spectra or spectrum generating functions.

At first, let us define three basic linear codes.

A \emph{single symbol repetition code} with a parameter $c \in \pintegers$ is a mapping $\repcode{q,c}: \field{q} \to \field{q}^c$ given by $x \mapsto (x, \ldots, x)$.

A \emph{single symbol check code} with a parameter $d \in \pintegers$ is a mapping  $\chkcode{q,d}: \field{q}^d \to \field{q}$ given by $\seq{x} \mapsto \sum_{i=1}^d x_i$, where the sum can be abbreviated as $(\seq{x})_{\oplus}$. In the sequel, we shall use this abbreviation to denote the sum of all components of a sequence (or vector).

A \emph{single symbol random multiplier code} is a random mapping $\rmcode{q}: \field{q} \to \field{q}$ given by $x \mapsto Cx$ where $C$ is an independent random variable uniformly distributed over $\fieldstar{q}$. Note that $\rmcode{q}$ has the following simple properties:
\begin{IEEEeqnarray*}{rCl}
a\rmcode{q} &\eqvar{d} &\rmcode{q} \qquad \forall a\in \fieldstar{q} \\
\rmcode{q} \circ \rmcode{q} &\eqvar{d} &\rmcode{q}.
\end{IEEEeqnarray*}

Based on the above codes, a random regular LDGM code $\ldcode{q,c,d,n}$ over $\field{q}$ is a mapping $\ldcode{q,c,d,n}: \mathbb{F}_q^{d'n} \to \mathbb{F}_q^{c'n}$ defined by
\begin{equation}\label{eq:DefinitionOfLDGMCode}
\ldcode{q,c,d,n} \eqdef \chkcode{q,d,c'n} \circ \rmcode{q,cd'n} \circ \Sigma_{cd'n} \circ \repcode{q,c,d'n}
\end{equation}
where $\repcode{q,c,n} \eqdef \bigpprod_{i=1}^n \repcode{q,c}$, $\chkcode{q,d,n} \eqdef \bigpprod_{i=1}^{n} \chkcode{q,d}$, $\rmcode{q,n} \eqdef \bigpprod_{i=1}^n \rmcode{q}$,
\begin{equation}\label{eq:DefinitionOfCDPrime}
c' = \frac{c}{(c,d)}, \quad d' = \frac{d}{(c,d)}
\end{equation}
and $(c,d)$ is the greatest common divisor of $c$ and $d$.

To calculate the joint spectrum of $\ldcode{q,c,d,n}$, we first need to calculate the joint spectra of its constituent codes. We note that the definition \eqref{eq:DefinitionOfLDGMCode} can be rewritten as
\begin{IEEEeqnarray}{rCl}
\ldcode{q,c,d,n} &\eqvar{d} &\rchkcode{q,d,c'n} \circ \Sigma_{cd'n} \circ \rrepcode{q,c,d'n} \IEEEnonumber \\
&\eqvar{d} &\rchkcode{q,d,c'n} \circ \Sigma_{cd'n} \circ \repcode{q,c,d'n} \IEEEnonumber \\
&\eqvar{d} &\chkcode{q,d,c'n} \circ \Sigma_{cd'n} \circ \rrepcode{q,c,d'n} \label{eq:DefinitionOfLDGMCode2}
\end{IEEEeqnarray}
where $\rrepcode{q,c,n} \eqdef \rmcode{q,cn} \circ \repcode{q,c,n} \circ \rmcode{q,n}$, $\rchkcode{q,d,n} \eqdef \rmcode{q,n} \circ \chkcode{q,d,n} \circ \rmcode{q,dn}$.
Then it suffices to calculate the joint spectra of $\repcode{q,c,n}$ and $\rchkcode{q,d,n}$. We have the following results.

\begin{proposition}\label{pr:SpectrumOfREPCode}
\begin{equation}\label{eq:SpectrumOfREPCodeA1}
\mathcal{G}(\repcode{q,c})(\seq{u}, \seq{v}) = \frac{1}{q} \sum_{a \in \field{q}} u_a v_a^c
\end{equation}
\begin{IEEEeqnarray}{l}
E[\mathcal{G}(\rrepcode{q,c})(\seq{u}, \seq{v})] \IEEEnonumber \\
\qquad = \frac{1}{q} u_{0} v_{0}^c + \frac{1}{q} ((\seq{u})_{\oplus} - u_0) \left( \frac{(\seq{v})_{\oplus} - v_0}{q-1} \right)^c \label{eq:SpectrumOfREPCodeA2}
\end{IEEEeqnarray}
\begin{equation}\label{eq:SpectrumOfREPCodeB}
\mathcal{G}(\repcode{q,c,n})(\seq{u}, \seq{v}) = \sum_{P \in \mathcal{P}_n(\field{q})} S(\field{q}^n)(P) \seq{u}^{nP} \seq{v}^{ncP}
\end{equation}
\begin{equation}\label{eq:SpectrumOfREPCodeC}
S(\repcode{q,c,n})(P, Q) = S(\mathbb{F}_q^n)(P) 1\{P = Q\}
\end{equation}
\begin{equation}\label{eq:SpectrumOfREPCodeD}
S(\repcode{q,c,n})(Q | P) = 1\{Q = P\}.
\end{equation}
\end{proposition}

\begin{proposition}\label{pr:SpectrumOfCHKCode}
\begin{IEEEeqnarray}{l}
E[\mathcal{G}(\rchkcode{q,d})(\seq{u}, \seq{v})] \IEEEnonumber \\
\quad = \frac{1}{q^{d+1}} \biggl[ ((\seq{u})_\oplus)^d (\seq{v})_\oplus + \biggl( \frac{qu_0 - (\seq{u})_\oplus}{q-1} \biggr)^d (qv_0 - (\seq{v})_\oplus) \biggr] \IEEEnonumber \\ \label{eq:SpectrumOfCHKCodeA}
\end{IEEEeqnarray}
\begin{equation}\label{eq:SpectrumOfCHKCodeB}
E[S(\rchkcode{q,d,n})(P, Q)] = \coef{g_{q,d,n}^{(1)}(\seq{u}, Q), \seq{u}^{dnP}}
\end{equation}
\begin{IEEEeqnarray}{l}
E[S(\rchkcode{q,d,n})(P, Q)] \le g_{q,d,n}^{(2)}(O,P,Q) \IEEEnonumber \\
\qquad \forall O \in \mathcal{P}_{dn}(\field{q}) \; (O(a) > 0, \forall a \in \{a|P(a) > 0\}) \label{eq:SpectrumOfCHKCodeC}
\end{IEEEeqnarray}
\begin{equation}\label{eq:SpectrumOfCHKCodeD}
\frac{1}{n} \ln \alpha(\rchkcode{q,d,n})(P, Q) \le \delta_{q,d}(P(0),Q(0)) + d\Delta_{q,dn}(P)
\end{equation}
where
\begin{IEEEeqnarray}{l}
g_{q,d,n}^{(1)}(\seq{u}, Q) \IEEEnonumber \\
\findent \eqdef \frac{{n \choose nQ}}{q^{n(d+1)}} \left[ ((\seq{u})_\oplus)^d + (q - 1) \left( \frac{qu_0 - (\seq{u})_\oplus}{q-1} \right)^d \right]^{nQ(0)} \IEEEnonumber \\
\findent \nullrel \breakop{\times} \left[ ((\seq{u})_\oplus)^d - \left( \frac{qu_0 - (\seq{u})_\oplus}{q-1} \right)^d \right]^{n(1-Q(0))} \label{eq:DefinitionOfCHKCodeGF1}
\end{IEEEeqnarray}
\begin{IEEEeqnarray}{l}
g_{q,d,n}^{(2)}(O, P, Q) \IEEEnonumber \\
\findent \eqdef \frac{{n \choose nQ}}{q^{n(d+1)} O^{dnP}} \left[ 1 + (q - 1) \left( \frac{qO(0) - 1}{q-1} \right)^d \right]^{nQ(0)} \IEEEnonumber \\
\findent \nullrel \breakop{\times} \left[ 1 - \left( \frac{qO(0) - 1}{q-1} \right)^d \right]^{n(1-Q(0))} \label{eq:DefinitionOfCHKCodeGF2}
\end{IEEEeqnarray}
\begin{IEEEeqnarray}{rCl}
\delta_{q,d}(x, y) &\eqdef &\inf_{0 < \hat{x} < 1} \delta_{q,d}(x, \hat{x}, y) \label{eq:DefinitionOfDelta} \\
\delta_{q,d}(x, \hat{x}, y) &\eqdef &dD(x \| \hat{x}) + J_{q,d}(\hat{x}, y) \label{eq:DefinitionOfDelta2} \\
J_{q,d}(x, y) &\eqdef &y \ln \left[ 1 + (q - 1) \left( \frac{qx - 1}{q-1} \right)^d \right] \IEEEnonumber \\
& &\breakop{+} (1 - y) \ln \left[ 1 - \left( \frac{qx - 1}{q-1} \right)^d \right] \label{eq:DefinitionOfJ} \\
\Delta_{q,n}(P) &\eqdef &H(P) - \frac{1}{n} \ln {n \choose nP}. \label{eq:DefinitionOfDelta3}
\end{IEEEeqnarray}
\end{proposition}

By Propositions~\ref{pr:SpectrumOfREPCode} and \ref{pr:SpectrumOfCHKCode}, we obtain a tight upper bound on the joint-spectrum performance of $\ldcode{q,c,d,n}$.

\begin{theorem}\label{th:SpectrumOfLDGMCode}
\begin{equation}\label{eq:SpectrumOfLDGMCodeA}
E[S(\ldcode{q,c,d,n})(Q|P)] = E[S(\rchkcode{q,d,c'n})(Q|P)]
\end{equation}
\begin{equation}\label{eq:SpectrumOfLDGMCodeB}
\frac{1}{d'n} \ln \alpha(\ldcode{q,c,d,n})(P,Q) \le \frac{c}{d}\delta_{q,d}(P(0),Q(0)) + c\Delta_{q,c'dn}(P)
\end{equation}
where $c'$ and $d'$ are defined by \eqref{eq:DefinitionOfCDPrime}, $\delta_{q,d}(x,y)$ is defined by \eqref{eq:DefinitionOfDelta}, and $\Delta_{q,n}(P)$ is defined by \eqref{eq:DefinitionOfDelta3}.
\end{theorem}

To have further insights into this bound, we analyze the properties of $\delta_{q,d}(x,y)$.

\begin{lemma}\label{le:UpperBoundOfDelta}
For all $x, y \in [0, 1]$,
\begin{equation}\label{eq:UpperBoundOfDelta}
\delta_{q,d}(x,y) \le J_{q,d}(x, y).
\end{equation}
\end{lemma}

\begin{lemma}\label{le:UpperBoundOfJ}
For all $x, y \in [0, 1]$,
\begin{equation}
J_{q,d}(x, y)
\le \ln \left[ 1 + (qy-1) \left( \frac{qx-1}{q-1} \right)^d \right] \label{eq:UpperBoundOfJ}.
\end{equation}
\end{lemma}

Based on the results above, the next theorem shows that for any $\delta > 0$, regular LDGM codes with $d$ large enough are approximately $\delta$-asymptotically SCC-good.

\begin{theorem}\label{th:ApproximateSCCGoodLDGMCode}
Let $\{\ldcode{q,c,d,n}\}_{n=1}^\infty$ be a sequence of random regular LDGM codes with the constant coding rate $r_0 = d/c$. Let $\{A_n\}_{n=1}^\infty$ be a sequence of sets $A_n \subseteq \mathcal{P}_{d'n}(\field{q})\backslash \{P_{0^{d'n}}\}$. Then
\begin{equation}
\limsup_{n \to \infty} \max_{\substack{P \in A_n,\\ Q \in \mathcal{P}_{c'n}(\field{q})}} \frac{1}{d'n} \ln \alpha(\ldcode{q,c,d,n})(P, Q) \le \rho_0
\end{equation}
where $c'$ and $d'$ are defined by \eqref{eq:DefinitionOfCDPrime}, and
\begin{equation}
\rho_0 \eqdef  \limsup_{n\to\infty}\max_{P \in A_n} \frac{1}{r_0} \ln\left[1+(q-1)\left| \frac{qP(0)-1}{q-1} \right|^d\right].
\end{equation}
If
\begin{equation}
A_n=\left\{P\in\mathcal{P}_{d'n}(\field{q}) \left| P(0)\in \left[\frac{1}{q}-\gamma_1,\frac{1}{q}+\gamma_2\right]\right.\right\}
\end{equation}
where $\gamma_1 \in (0,1/q] \backslash \{\frac{1}{2}\}$ and $\gamma_2 \in (0,(q-1)/q)$, then
\begin{equation}
\rho_0 = \frac{1}{r_0} \ln\left[1+(q-1)\left(\frac{q\gamma}{q-1}\right)^d\right]
\end{equation}
where $\gamma \eqdef \max\{\gamma_1,\gamma_2\}$. For any $\delta>0$, define
\begin{equation}
d_q(\gamma,\delta)\eqdef\ceil{\frac{\ln[(e^{r_0 \delta}-1)/(q-1)]}{\ln[q\gamma/(q-1)]}}.
\end{equation}
Then we have $\rho_0 \le \delta$ for all $d \ge d_q(\gamma,\delta)$.
\end{theorem}

Theorem~\ref{th:ApproximateSCCGoodLDGMCode} together with Theorem~\ref{th:ConstructionOfGoodLSCC} and Remark~\ref{re:ConstructionOfGoodLSCC} shows that, for any $\delta > 0$, we can construct $\delta$-asymptotically good LSCCs by a serial concatenation of an inner LDGM code and an outer linear code with good distance properties. In particular, we may use LDPC codes as outer codes. Furthermore, Proposition~\ref{pr:DiagonalArgument} shows that we can find a sequence of asymptotically good LSCCs in a family of sequences of $\delta_i$-asymptotically good LSCCs, where $\delta_i$ is decreasing in $i$ and converges to zero as $i \to \infty$. An analogous construction was proposed by Hsu in his Ph.D. dissertation \cite{JSCC:Hsu200600}, but his purpose was only to find good channel codes and only a rate-1 LDGM code was employed as an inner code in his construction.

Next, we give an example to show how we determine the parameters of the inner LDGM code when designing such codes.

\begin{example}
Let $\delta=0.05$ and $f_n: \field{2}^n \to \field{2}^{5n}$ an injective linear code. Suppose that the normalized weight of all nonzero codewords of $f_n$ ranges from $0.05$ to $0.95$. We shall design a linear code $H_n: \field{2}^n \to \field{2}^{2n}$ that is $\delta$-asymptotically SCC-good. Let $H_n = G_n \circ \Sigma_{5n} \circ f_n$ where $G_n$ is a random regular LDGM code over $\field{2}$. It is clear that the coding rate of $G_n$ must be $\frac{5}{2}$. Using Theorem~\ref{th:ApproximateSCCGoodLDGMCode} with $q=2$, $r_0=\frac{5}{2}$, and $\gamma_1=\gamma_2=0.45$, we have $d_q(\gamma, \delta R(f_n))=35$. Then we may choose LDGM codes with $c=14$ and $d=35$, so that $\rho_0 \le 0.01$, and therefore $\limsup_{n \to \infty} \rho(H_n) \le \rho_0 / R(f_n) = 0.05$.
\end{example}

So far, we have presented two families of good linear codes, one based on Gabidulin codes (Section~\ref{subsec:MRDLSCC}) and the other based on LDGM codes. It is necessary to give some comparisons of these two families of codes. At first glance, it seems that the family based on Gabidulin codes is better than that based on LDGM codes since the former is SCC-good while the latter is only asymptotically SCC-good. However, this is not the truth, because there is no single linear code that is SCC-good. The proposition that follows states the fact. Consequently, in terms of code spectrum, the two families have almost the same performance. On the other hand, in terms of decoding complexities, the family based on LDGM codes is more competitive than that based on Gabidulin codes, since LDGM codes as well as LDPC codes are all characterized by sparse matrices so that low-complexity iterative decoding algorithms can be employed.

\begin{proposition}\label{pr:SingleCodeSpectrum}
For any linear code $f: \mathcal{X}^n \to \mathcal{Y}^m$ with $|\mathcal{X}|\ge 2$,
\[
\max_{\substack{P \in \mathcal{P}_n(\mathcal{X})\backslash \{P_{0^n}\} \\ Q \in \mathcal{P}_m(\mathcal{Y})}} \alpha(f)(P,Q) \ge \order\left(m^{\frac{|\mathcal{Y}|-1}{2}}\right).
\]
\end{proposition}

The proofs are given in Section~\ref{subsec:ProofOfExplicitConstruction}.

\section{Proofs}\label{sec:Proofs}


\subsection{Proofs of Results in Section \ref{subsec:NewResultsI}}\label{subsec:ProofOfNewResultsI}

\begin{proofof}{Proposition \ref{pr:SpectrumProperty2UnderVectorPermutation}}
It is clear that, for any $\seq{x}_{\mathcal{I}_m}$ and $\hat{\seq{x}}_{\mathcal{I}_m}$ satisfying $P_{\seq{x}_i} = P_{\hat{\seq{x}}_i}$ for each $i \in \mathcal{I}_m$,
\begin{IEEEeqnarray*}{rCl}
E\left[ \frac{1\{\seq{x}_{\mathcal{I}_m} \in \tilde{A}\}}{|A|} \right]
&= &E\left[ \frac{1\{\seq{x}_{\mathcal{I}_m} \in \tilde{A}\}}{|\tilde{A}|} \right] \\
&\eqvar{(a)} &E\left[ \frac{1\{\hat{\seq{x}}_{\mathcal{I}_m} \in \tilde{A}\}}{|\tilde{A}|} \right] \\
&= &E\left[ \frac{1\{\hat{\seq{x}}_{\mathcal{I}_m} \in \tilde{A}\}}{|A|} \right]
\end{IEEEeqnarray*}
where (a) follows from the property that the distribution of $\tilde{A}$ is invariant under any permutation. Then it follows that
\begin{IEEEeqnarray*}{l}
E\left[ \frac{1\{\seq{x}_{\mathcal{I}_m} \in \tilde{A}\}}{|A|} \right] \\
\findent = \frac{1}{\prod_{i=1}^m |\mathcal{T}_{P_{\seq{x}_i}}^{n_i}(\mathcal{X}_i)|} \sum_{\hat{\seq{x}}_{\mathcal{I}_m} \in \prod_{i=1}^m \mathcal{T}_{P_{\seq{x}_i}}^{n_i}(\mathcal{X}_i)} E\left[ \frac{1\{\hat{\seq{x}}_{\mathcal{I}_m} \in \tilde{A}\}}{|A|} \right] \\
\findent = \frac{1}{\prod_{i=1}^m |\mathcal{T}_{P_{\seq{x}_i}}^{n_i}(\mathcal{X}_i)|} E \left[ \sum_{\hat{\seq{x}}_{\mathcal{I}_m} \in \prod_{i=1}^m \mathcal{T}_{P_{\seq{x}_i}}^{n_i}(\mathcal{X}_i)} \frac{1\{\hat{\seq{x}}_{\mathcal{I}_m} \in \tilde{A}\}}{|A|} \right] \\
\findent = \frac{1}{\prod_{i=1}^m {n_i \choose n_i P_{\seq{x}_i}}} E \left[ \frac{\left|\tilde{A} \cap \prod_{i=1}^m \mathcal{T}_{P_{\seq{x}_i}}^{n_i}(\mathcal{X}_i)\right|}{|A|} \right] \\
\findent = \frac{1}{\prod_{i=1}^m {n_i \choose n_i P_{\seq{x}_i}}} E \left[ \frac{\left|A \cap \prod_{i=1}^m \mathcal{T}_{P_{\seq{x}_i}}^{n_i}(\mathcal{X}_i)\right|}{|A|} \right] \\
\findent \eqvar{(a)} \frac{\alpha(A)((P_{\seq{x}_i})_{i \in \mathcal{I}_m})}{\prod_{i=1}^m |\mathcal{X}_i|^{n_i}}
\end{IEEEeqnarray*}
where (a) follows from the definition of joint spectrum and Proposition~\ref{pr:SpectrumOfSets}. This concludes \eqref{eq:SpectrumProperty21UnderVectorPermutation}, and the identity \eqref{eq:SpectrumProperty22UnderVectorPermutation} comes from
\begin{IEEEeqnarray*}{l}
E\left[ \frac{\left|\left( \seq{x}_{\mathcal{I}_l} \times \prod_{i=l+1}^m \mathcal{T}_{P_i}^{n_i}(\mathcal{X}_i)\right) \cap \tilde{A}\right|}{|A|} \right] \\
\findent = E\left[ \sum_{\hat{\seq{x}}_{\mathcal{I}_m \backslash \mathcal{I}_l} \in \prod_{i=l+1}^m \mathcal{T}_{P_i}^{n_i}(\mathcal{X}_i)} \frac{1\{ (\seq{x}_{\mathcal{I}_l}, \hat{\seq{x}}_{\mathcal{I}_m \backslash \mathcal{I}_l}) \in \tilde{A}\}}{|A|} \right] \\
\findent = \sum_{\hat{\seq{x}}_{\mathcal{I}_m \backslash \mathcal{I}_l} \in \prod_{i=l+1}^m \mathcal{T}_{P_i}^{n_i}(\mathcal{X}_i)} E \left[ \frac{1\{ (\seq{x}_{\mathcal{I}_l}, \hat{\seq{x}}_{\mathcal{I}_m \backslash \mathcal{I}_l}) \in \tilde{A} \}}{|A|} \right]
\end{IEEEeqnarray*}
combined with \eqref{eq:SpectrumProperty21UnderVectorPermutation} and Proposition~\ref{pr:SpectrumOfSets}.
\end{proofof}


\subsection{Proofs of Results in Section \ref{subsec:NewResultsII}}\label{subsec:ProofOfNewResultsII}

\begin{proofof}{Proposition \ref{pr:SpectrumPropertyX1OfFunctions}}
\begin{IEEEeqnarray*}{l}
P\left\{\rtilde{F}(\seq{x}_{\mathcal{I}_l}) \in \prod_{j=1}^k \mathcal{T}_{Q_j}^{m_j}(\mathcal{Y}_j)\right\} \\
\findent = P\left\{\tilde{F}(\seq{x}_{\mathcal{I}_l}) \in \prod_{j=1}^k \mathcal{T}_{Q_j}^{m_j}(\mathcal{Y}_j)\right\} \\
\findent = E\left[ 1\left\{ \tilde{F}(\seq{x}_{\mathcal{I}_l}) \in \prod_{j=1}^k \mathcal{T}_{Q_j}^{m_j}(\mathcal{Y}_j)\right\}\right] \\
\findent = E\left[ \sum_{\seq{y}_{\mathcal{I}_m} \in \prod_{j=1}^k \mathcal{T}_{Q_j}^{m_j}(\mathcal{Y}_j)} 1\{ ( \seq{x}_{\mathcal{I}_l}, \seq{y}_{\mathcal{I}_m} ) \in \mathrm{rl}(\tilde{F}) \} \right] \\
\findent = E\left[ \sum_{\seq{y}_{\mathcal{I}_m} \in \prod_{j=1}^k \mathcal{T}_{Q_j}^{m_j}(\mathcal{Y}_j)} 1\{ ( \seq{x}_{\mathcal{I}_l}, \seq{y}_{\mathcal{I}_m} ) \in \widetilde{\mathrm{rl}(F)} \} \right] \\
\findent = E\left[ \left| \left( \seq{x}_{\mathcal{I}_l} \times \prod_{j=1}^k \mathcal{T}_{Q_j}^{m_j}(\mathcal{Y}_j) \right) \cap \widetilde{\mathrm{rl}(F)} \right| \right] \\
\findent \eqvar{(a)} \frac{E[S_{\mathcal{X}_1 \cdots \mathcal{X}_l \mathcal{Y}_1 \cdots \mathcal{Y}_m}(F)((P_{\seq{x}_i})_{i \in \mathcal{I}_l}, Q_{\mathcal{I}_k})]}{\prod_{i=1}^l S_{\mathcal{X}_i}(\mathcal{X}_i^{n_i})(P_{\seq{x}_i})} \\
\findent = E[S_{\mathcal{Y}_1 \cdots \mathcal{Y}_k | \mathcal{X}_1 \cdots \mathcal{X}_l}(F)(Q_{\mathcal{I}_k}|(P_{\seq{x}_i})_{i \in \mathcal{I}_l})]
\end{IEEEeqnarray*}
where (a) follows from Proposition~\ref{pr:SpectrumProperty2UnderVectorPermutation} and the identity $|\mathrm{rl}(F)| = \prod_{i=1}^l |\mathcal{X}_i|^{n_i}$.
\end{proofof}

\begin{proofof}{Proposition \ref{pr:SpectrumOfSeriallyConcatenatedFunctions}}
\begin{IEEEeqnarray*}{l}
E[S_{\mathcal{Z}|\mathcal{X}}(G \circ \Sigma_m \circ F)(Q|O)] \\
\findent \eqvar{(a)} P\{(\rtilde{G} \circ \rtilde{F})(\seq{x}) \in \mathcal{T}_Q^l(\mathcal{Z})\} \\
\findent = \sum_{P \in \mathcal{P}_m(\mathcal{Y})} P\{\rtilde{F}(\seq{x}) \in \mathcal{T}_P^m(\mathcal{Y}), \rtilde{G}(\rtilde{F}(\seq{x})) \in \mathcal{T}_Q^l(\mathcal{Z})\} \\
\findent = \sum_{P \in \mathcal{P}_m(\mathcal{Y})} \bigg( P\{\rtilde{F}(\seq{x}) \in \mathcal{T}_P^m(\mathcal{Y})\} \\
\findent \nullrel \breakop{\times} P\{\rtilde{G}(\rtilde{F}(\seq{x})) \in \mathcal{T}_Q^l(\mathcal{Z}) | \rtilde{F}(\seq{x}) \in \mathcal{T}_P^m(\mathcal{Y})\} \bigg) \\
\findent \eqvar{(b)} \sum_{P \in \mathcal{P}_m(\mathcal{Y})} E[S_{\mathcal{Y}|\mathcal{X}}(F)(P|O)] E[S_{\mathcal{Z}|\mathcal{Y}}(G)(Q|P)]
\end{IEEEeqnarray*}
where (a) and (b) follow from Proposition~\ref{pr:SpectrumPropertyX1OfFunctions}, and $\seq{x}$ is an arbitrary sequence such that $P_{\seq{x}} = O$.
\end{proofof}


\subsection{Proofs of Results in Section \ref{subsec:NewResultsIIIpre}}\label{subsec:ProofOfNewResultsIIIpre}

\begin{proofof}{Proposition \ref{pr:RenameGeneratingFunction}}
At first, we explicitly write $F_n = \bigpprod_{i=1}^n F^{(i)}$ and $G_m = \bigpprod_{i=1}^m G^{(i)}$ where $F^{(i)}$ and $G^{(i)}$ are the $i$th independent copies of $F$ and $G$, respectively.

Next, let $B' = (F_n \pprod G_m)(B)$. Since both $F_n$ and $G_m$ are bijective, the generating function $\mathcal{G}(B')(\seq{u},\seq{v})$ can be rewritten as
\begin{IEEEeqnarray*}{l}
\mathcal{G}(B')(\seq{u},\seq{v}) \\
\findent = \frac{1}{|B'|} \sum_{\seq{x},\seq{y}} 1\{(\seq{x},\seq{y}) \in B'\} \seq{u}^{nP_{\seq{x}}} \seq{v}^{mP_{\seq{y}}} \\
\findent = \frac{1}{|B|} \sum_{\seq{x},\seq{y}} 1\{(\seq{x},\seq{y}) \in B\} \prod_{i=1}^n u_{F^{(i)}(x_i)} \prod_{j=1}^m v_{G^{(j)}(y_j)}
\end{IEEEeqnarray*}
Taking the expectation on both sides, we obtain
\begin{IEEEeqnarray*}{l}
E[\mathcal{G}(B')(\seq{u},\seq{v})] \\
\findent = \sum_{\seq{x},\seq{y}} E\left[\frac{1\{(\seq{x},\seq{y}) \in B\}}{|B|}\right] \prod_{i=1}^n E[u_{F(x_i)}] \prod_{j=1}^m E[v_{G(y_j)}] \\
\findent = E{\left[\mathcal{G}(B)((E[u_{F(a)}])_{a\in\mathcal{X}},(E[v_{G(b)}])_{b\in\mathcal{Y}})\right]}
\end{IEEEeqnarray*}
which is just the expectation $E[\mathcal{G}(B)(\seq{u},\seq{v})]$ with substitutions \eqref{eq:RenameSubstitutionRuleX} and \eqref{eq:RenameSubstitutionRuleY}.
\end{proofof}


\subsection{Proofs of Results in Section \ref{subsec:NewResultsIII}}\label{subsec:ProofOfNewResultsIII}

\begin{proofof}{Proposition \ref{pr:GeneratingFunctionOfProductOfSets}}
By the definition of spectrum generating functions, we have
\begin{IEEEeqnarray*}{rCl}
\mathcal{G}(A \times B)(\seq{u}, \seq{v})
&= &\frac{1}{|A \times B|} \sum_{(\seq{x}, \seq{y}) \in A \times B} \seq{u}^{nP_{\seq{x}}} \seq{v}^{mP_{\seq{y}}} \\
&= &\frac{1}{|A|} \sum_{\seq{x} \in A} \seq{u}^{nP_{\seq{x}}} \cdot \frac{1}{|B|} \sum_{\seq{y} \in B} \seq{v}^{mP_{\seq{y}}} \\
&= &\mathcal{G}(A)(\seq{u}) \cdot \mathcal{G}(B)(\seq{v}).
\end{IEEEeqnarray*}
\end{proofof}

\begin{proofof}{Proposition \ref{pr:SubstitutionPrincipleOfGeneratingFunction}}
Since $\mathcal{U}_2$ is a refinement of $\mathcal{U}_1$,
\begin{IEEEeqnarray*}{rCl}
\mathcal{G}_{\mathcal{X}^{\mathcal{U}_2}}(A)(\seq{u}_{2,\mathcal{U}_2}) &= &\frac{1}{|A|} \sum_{\seq{x} \in A} \prod_{U_2 \in \mathcal{U}_2} \seq{u}_{2,U_2}^{|U_2|P^{U_2}_{\seq{x}}} \\
&= &\frac{1}{|A|} \sum_{\seq{x} \in A} \prod_{U_1 \in \mathcal{U}_1} \prod_{\substack{U_2 \in \mathcal{U}_2,\\ U_2 \subseteq U_{1}}} \seq{u}_{2,U_2}^{|U_{2}|P^{U_{2}}_{\seq{x}}}.
\end{IEEEeqnarray*}
Applying the substitution \eqref{eq:SubstitutionRule} and the identity
$$
\sum_{\substack{U_2 \in \mathcal{U}_2,\\ U_2 \subseteq U_{1}}} |U_{2}| P^{U_{2}}_{\seq{x}}(a) = |U_{1}| P^{U_{1}}_{\seq{x}}(a) \qquad \forall a \in \mathcal{X}
$$
we obtain the generating function $\mathcal{G}_{\mathcal{X}^{\mathcal{U}_1}}(A)(\seq{u}_{1,\mathcal{U}_1})$.
\end{proofof}

\begin{proofof}{Corollary \ref{co:GeneratingFunctionOfSetProduct}}
\begin{IEEEeqnarray*}{rCl}
\mathcal{G}_{\mathcal{X}}(A_1 \times A_2)(\seq{u})
&\eqvar{(a)} &\mathcal{G}_{\mathcal{X}^2}(A_1 \times A_2)(\seq{u}, \seq{u}) \\
&\eqvar{(b)} &\mathcal{G}_{\mathcal{X}}(A_1)(\seq{u}) \cdot \mathcal{G}_{\mathcal{X}}(A_2)(\seq{u})
\end{IEEEeqnarray*}
where (a) follows from Proposition~\ref{pr:SubstitutionPrincipleOfGeneratingFunction} and (b) follows from Proposition~\ref{pr:GeneratingFunctionOfProductOfSets}.
\end{proofof}

\begin{proofof}{Corollary \ref{co:GeneratingFunctionOfFunctionParallelProduct}}
\begin{IEEEeqnarray*}{rCl}
\mathcal{G}_{\mathcal{X}\mathcal{Y}}(f_1 \pprod f_2)(\seq{u}, \seq{v})
&\eqvar{(a)} &\mathcal{G}_{\mathcal{X}\mathcal{Y}\mathcal{X}\mathcal{Y}}(f_1 \pprod f_2)(\seq{u}, \seq{v}, \seq{u}, \seq{v}) \\
&\eqvar{(b)} &\mathcal{G}_{\mathcal{X}\mathcal{Y}}(f_1)(\seq{u}, \seq{v}) \cdot \mathcal{G}_{\mathcal{X}\mathcal{Y}}(f_2)(\seq{u}, \seq{v})
\end{IEEEeqnarray*}
where (a) follows from $\mathrm{rl}(f_1 \pprod f_2) \subseteq \mathcal{X}^{n_1} \times \mathcal{X}^{n_2} \times \mathcal{Y}^{m_1} \times \mathcal{Y}^{m_2}$ and Proposition~\ref{pr:SubstitutionPrincipleOfGeneratingFunction} with the default partition, and (b) follows from Proposition~\ref{pr:GeneratingFunctionOfProductOfSets} with $\mathrm{rl}(f_1 \pprod f_2) = \mathrm{rl}(f_1) \times \mathrm{rl}(f_2)$.
\end{proofof}


\subsection{Proofs of Results in Section \ref{subsec:NewResultsV}}\label{subsec:ProofOfNewResultsV}

To prove Theorem \ref{th:MacWilliamsIdentitiesF}, we first need two lemmas.

\begin{lemma}\label{le:MacWilliamsIdentities1F}
Let $A$ be a subspace of $\field{q}^n$. Then
\begin{equation}\label{eq:MacWilliamsIdentitiesLemma1}
\frac{1}{|A|} \sum_{\seq{x}_1 \in A} \chi(\seq{x}_1 \cdot \seq{x}_2) = 1\{\seq{x}_2 \in A^{\perp}\} \qquad \forall \seq{x}_2 \in \field{q}^n.
\end{equation}
\end{lemma}

\begin{proof}
For a fixed $\seq{x}_2$, the mapping $\tau: A \to \field{q}$ given by $\seq{x} \mapsto \seq{x} \cdot \seq{x}_2$ is an $\field{q}$-module homomorphism of $A$ into $\field{q}$, and hence the image set $\tau(A) \subseteq \field{q}$ is also a vector space over $\field{q}$, which must be either $0$ or $\field{q}$.

If $\seq{x}_2 \in A^{\perp}$, then $\chi(\seq{x}_1 \cdot \seq{x}_2) = \chi(0) = 1$ for all $\seq{x}_1 \in A$, and hence the identity \eqref{eq:MacWilliamsIdentitiesLemma1} holds. If however $\seq{x}_2 \not \in A^{\perp}$, then
\[
\frac{1}{|A|} \sum_{\seq{x}_1 \in A} \chi(\seq{x}_1 \cdot \seq{x}_2)
= \frac{1}{q} \sum_{a \in \field{q}} \chi(a)
= 0.
\]
The last equality follows from the property \eqref{eq:ChiPropertyF}.
\end{proof}

\begin{lemma}\label{le:MacWilliamsIdentities2F}
Let $\mathcal{U}$ be a fixed partition of $\mathcal{I}_n$. Then
$$
\sum_{\seq{x}_2 \in \field{q}^n} \chi(\seq{x}_1 \cdot \seq{x}_2) \prod_{U \in \mathcal{U}} \seq{u}_U^{|U|P^{U}_{\seq{x}_2}} = \prod_{U \in \mathcal{U}} (\seq{u}_U \mat{M})^{|U| P^{U}_{\seq{x}_1}}
$$
for all $\seq{x}_1 \in \field{q}^n$, where $\mat{M}$ is defined by \eqref{eq:MacWilliamsMatrixF}.
\end{lemma}

\begin{proof}
\begin{IEEEeqnarray*}{l}
\sum_{\seq{x}_2 \in \field{q}^n} \chi(\seq{x}_1 \cdot \seq{x}_2) \prod_{U \in \mathcal{U}} \seq{u}_U^{|U|P^{U}_{\seq{x}_2}} \\
\findent \eqvar{(a)} \sum_{\seq{x}_2 \in \field{q}^n} \prod_{U \in \mathcal{U}} \prod_{i \in U} \chi(x_{1,i} x_{2,i}) u_{U,x_{2,i}} \\
\findent = \prod_{U \in \mathcal{U}} \prod_{i \in U} \sum_{a_2 \in \field{q}} \chi(x_{1,i} a_2) u_{U,a_2} \\
\findent = \prod_{U \in \mathcal{U}} \prod_{a_1 \in \field{q}} \left( \sum_{a_2 \in \field{q}} \chi(a_1 a_2) u_{U,a_2} \right)^{|U| P^{U}_{\seq{x}_1}(a_1)} \\
\findent = \prod_{U \in \mathcal{U}} (\seq{u}_U \mat{M})^{|U| P^{U}_{\seq{x}_1}}
\end{IEEEeqnarray*}
where (a) follows from the identities
$$
\chi(\seq{x}_1 \cdot \seq{x}_2) = \chi(\sum_{i=1}^n x_{1,i} x_{2,i}) = \prod_{i=1}^n \chi(x_{1,i} x_{2,i})
$$
and
$$
\seq{u}_U^{|U|P^{U}_{\seq{x}_2}} = \prod_{i \in U} u_{U,x_{2,i}}.
$$
\end{proof}

\begin{proofof}{Theorem \ref{th:MacWilliamsIdentitiesF}}
\begin{IEEEeqnarray*}{l}
\mathcal{G}_{\field{q}^{\mathcal{U}}}(A^{\perp})(\seq{u}_{\mathcal{U}}) \\
\findent = \frac{1}{|A^{\perp}|} \sum_{\seq{x}_2 \in A^{\perp}} \prod_{U \in \mathcal{U}} \seq{u}_U^{|U|P^{U}_{\seq{x}_2}} \\
\findent = \frac{1}{|A^{\perp}|} \sum_{\seq{x}_2 \in \field{q}^n} 1\{\seq{x}_2 \in A^{\perp}\} \prod_{U \in \mathcal{U}} \seq{u}_U^{|U|P^{U}_{\seq{x}_2}} \\
\findent \eqvar{(a)} \frac{1}{|A^{\perp}|} \sum_{\seq{x}_2 \in \field{q}^n} \frac{1}{|A|} \sum_{\seq{x}_1 \in A} \chi(\seq{x}_1 \cdot \seq{x}_2) \prod_{U \in \mathcal{U}} \seq{u}_U^{|U|P^{U}_{\seq{x}_2}} \\
\findent = \frac{1}{|A||A^{\perp}|} \sum_{\seq{x}_1 \in A} \sum_{\seq{x}_2 \in \field{q}^n} \chi(\seq{x}_1 \cdot \seq{x}_2) \prod_{U \in \mathcal{U}} \seq{u}_U^{|U|P^{U}_{\seq{x}_2}} \\
\findent \eqvar{(b)} \frac{1}{|A||A^{\perp}|} \sum_{\seq{x}_1 \in A} \prod_{U \in \mathcal{U}} (\seq{u}_U \mat{M})^{|U| P^{U}_{\seq{x}_1}} \\
\findent = \frac{1}{|A^{\perp}|} \mathcal{G}_{\mathcal{X}^\mathcal{U}}(A)((\seq{u}_U \mat{M})_{U \in \mathcal{U}})
\end{IEEEeqnarray*}
where (a) follows from Lemma~\ref{le:MacWilliamsIdentities1F}, and (b) from Lemma~\ref{le:MacWilliamsIdentities2F}.
\end{proofof}

\begin{proofof}{Theorem \ref{th:MacWilliamsIdentitiesJF}}
Define the sets
$$
Z_1 \eqdef \{(\seq{x}\mat{A}, \seq{x}) \in \field{q}^m \times \field{q}^n | \seq{x} \in \field{q}^n\}
$$
and
$$
Z_2 \eqdef \{(\seq{y}, -\seq{y}\transpose{\mat{A}}) \in \field{q}^m \times \field{q}^n | \seq{y} \in \field{q}^m\}.
$$
Clearly, for any $\seq{z}_1 = (\seq{x}\mat{A}, \seq{x}) \in Z_1$ and $\seq{z}_2 = (\seq{y}, -\seq{y}\transpose{\mat{A}}) \in Z_2$, we have
\begin{IEEEeqnarray*}{rCl}
\seq{z}_1 \cdot \seq{z}_2
&= &(\seq{x}\mat{A}) \cdot \seq{y} + \seq{x} \cdot (-\seq{y}\transpose{\mat{A}}) \\
&= &(\seq{x}\mat{A}) \transpose{\seq{y}} - \seq{x} \transpose{(\seq{y}\transpose{\mat{A}})} \\
&= &\seq{x}\mat{A}\transpose{\seq{y}} - \seq{x}\mat{A}\transpose{\seq{y}} \\
&= &0
\end{IEEEeqnarray*}
which implies $Z_2 \subseteq Z_1^{\perp}$. Note that $|Z_1||Z_2| = q^{m+n}$. This, together with the identity $|Z_1||Z_1^{\perp}| = q^{m+n}$, gives $Z_2 = Z_1^{\perp}$.

Then it follows from Theorem~\ref{th:MacWilliamsIdentitiesF} that
\begin{IEEEeqnarray*}{l}
\mathcal{G}_{\field{q}^{\mathcal{V}}\field{q}^{\mathcal{U}}}(-g)(\seq{v}_{\mathcal{V}}, \seq{u}_{\mathcal{U}}) \\
\findent = \mathcal{G}_{\field{q}^{\mathcal{V}}\field{q}^{\mathcal{U}}}(Z_2)(\seq{v}_{\mathcal{V}}, \seq{u}_{\mathcal{U}}) \\
\findent = \mathcal{G}_{\field{q}^{\mathcal{V}}\field{q}^{\mathcal{U}}}(Z_1^{\perp})(\seq{v}_{\mathcal{V}}, \seq{u}_{\mathcal{U}}) \\
\findent = \frac{1}{|Z_1^{\perp}|} \mathcal{G}_{\field{q}^{\mathcal{V}}\field{q}^{\mathcal{U}}}(Z_1)((\seq{v}_V \mat{M})_{V \in \mathcal{V}}, (\seq{u}_U \mat{M})_{U \in \mathcal{U}}) \\
\findent = \frac{1}{q^m} \mathcal{G}_{\field{q}^{\mathcal{U}}\field{q}^{\mathcal{V}}}(f)((\seq{u}_U \mat{M})_{U \in \mathcal{U}}, (\seq{v}_V \mat{M})_{V \in \mathcal{V}})
\end{IEEEeqnarray*}
as desired.
\end{proofof}

\begin{proof}[Sketch of Proof of Theorem \ref{th:MacWilliamsIdentities}]
Establish an analogue of Lemma~\ref{le:MacWilliamsIdentities1F} by using the fact that the kernel of a generating character contains no nonzero ideal. Then use an argument similar to that of Theorem~\ref{th:MacWilliamsIdentitiesF}.
\end{proof}


\subsection{Proofs of Results in Section \ref{sec:ConceptsOfGoodLinearCodes}}\label{subsec:ProofOfConceptsOfGoodLinearCodes}

\begin{proofof}{Proposition~\ref{pr:KernelSpectrumCondition}}
For any $\epsilon > 0$, define the sequence of events
$$
A_k = \left\{ \omega \in \Omega \left| \left| R_s(\rtilde{F}_k) - R_s(\seqx{F}) \right| \le \frac{\epsilon}{3} \right.\right\}.
$$
It is clear that $\lim_{k \to \infty} P(A_k) = 1$, so that the conditions \eqref{eq:OriginalDefinitionX1OfAsympGoodLSC} and \eqref{eq:OriginalDefinitionX2OfAsympGoodLSC} hold. Furthermore, we have
\begin{IEEEeqnarray*}{l}
\max_{\seq{x}: \seq{x} \ne 0^{n_k}} \frac{1}{n_k} \ln P\{\seq{x} \in \ker \rtilde{F}_k | A_k\} \\
\findent = \max_{\seq{x}: \seq{x} \ne 0^{n_k}} \frac{1}{n_k} \ln E\left[\left.\frac{|\mathcal{X}|^{n_k} 1\{\seq{x} \in \ker \rtilde{F}_k\}}{|\rtilde{F}_k(\mathcal{X}^{n_k})| |\ker \rtilde{F}_k|} \right| A_k \right] \\
\findent \le \max_{\seq{x}: \seq{x} \ne 0^{n_k}} \frac{1}{n_k} \ln \left( \frac{|\mathcal{X}|^{n_k}}{e^{n_k(R_s(\seqx{F}) - \frac{\epsilon}{3})}} E\left[\left.\frac{1\{\seq{x} \in \widetilde{\ker F_k}\}}{|\ker F_k|} \right| A_k \right] \right) \\
\findent \le -R_s(\seqx{F}) + \frac{\epsilon}{3} \\
\findent \nullrel \breakop{+} \max_{\seq{x}: \seq{x} \ne 0^{n_k}} \frac{1}{n_k} \ln \left( \frac{|\mathcal{X}|^{n_k}}{P(A_k)}E\left[\frac{1\{\seq{x} \in \widetilde{\ker F_k}\}}{|\ker F_k|} \right] \right) \\
\findent \levar{(a)} -R_s(\seqx{F}) + \frac{2\epsilon}{3} + \max_{P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}} \frac{1}{n_k} \ln \alpha(\ker F_k)(P) \\
\findent \levar{(b)} -R_s(\seqx{F}) + \delta + \epsilon
\end{IEEEeqnarray*}
for sufficiently large $k$, where (a) follows from Proposition~\ref{pr:SpectrumProperty2UnderVectorPermutation} and $\lim_{k \to \infty} P(A_k) = 1$, and (b) follows from \eqref{eq:DefinitionOfAsympGoodLSC}. This concludes \eqref{eq:OriginalDefinition2OfAsympGoodLSC} and hence proves the proposition.
\end{proofof}

\begin{proofof}{Proposition \ref{pr:ImageSpectrumCondition}}
Use argument similar to that of Proposition~\ref{pr:KernelSpectrumCondition}.
\end{proofof}

\begin{proofof}{Proposition \ref{pr:JointSpectrumCondition}}
Apply Proposition~\ref{pr:SpectrumPropertyOfFunctions}.
\end{proofof}

\begin{proof}[Sketch of Proof of Proposition \ref{pr:RelationBetweenLSCandLCC}]
Using the Kronecker decomposition theorem, we can always find a group $\mathcal{X}^{l_k}$ for some $l_k$ and a random linear code $G_k: \mathcal{X}^{l_k} \to \mathcal{X}^{n_k}$ (does not have to be injective) such that $G_k(\mathcal{X}^{l_n}) = \ker F_k$, and hence $G_k$ is a $\delta$-asymptotically good LCC.
\end{proof}

\begin{proof}[Sketch of Proof of Proposition \ref{pr:RelationBetweenLCCandLSC}]
Using the Kronecker decomposition theorem, we can always find a group $\mathcal{Y}^{l_k}$ for some $l_k$ and a random linear code $G_k: \mathcal{Y}^{m_k} \to \mathcal{Y}^{l_k}$ such that $\ker G_k = F_k(\mathcal{X}^{n_k})$, and hence $G_k$ is a $\delta$-asymptotically good LSC.
\end{proof}

\begin{proofof}{Proposition \ref{pr:RelationBetweenLSCCandLSCLCC}}
It follows from \eqref{eq:DefinitionOfAsympGoodLSCC} that
\begin{equation}\label{eq:ProofEq1OfRelationBetweenLSCCandLSCLCC}
\max_{\scriptstyle P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\} \atop \scriptstyle Q \in \mathcal{P}_{m_k}(\mathcal{Y})} \frac{1}{n_k} \ln \alpha(F_k)(P, Q) \le \delta + \epsilon
\end{equation}
for any $\epsilon > 0$ and sufficiently large $k$. Then it follows that
\begin{IEEEeqnarray*}{l}
\max_{P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}} \frac{1}{n_k} \ln \alpha(\ker F_k)(P) \\
\findent \eqvar{(a)} \max_{\seq{x}: \seq{x} \ne 0^{n_k}} \frac{1}{n_k} \ln \left( E\left[\frac{|\mathcal{X}|^{n_k} 1\{\seq{x} \in \widetilde{\ker F_k}\}}{|\ker F_k|}\right] \right) \\
\findent \le \max_{\seq{x}: \seq{x} \ne 0^{n_k}} \frac{1}{n_k} \ln (|\mathcal{Y}|^{m_k} P\{\rtilde{F}_k(\seq{x}) = 0^{m_k}\}) \\
\findent = \max_{\seq{x}: \seq{x} \ne 0^{n_k}} \frac{1}{n_k} \ln \left( |\mathcal{Y}|^{m_k} P\{\tilde{F}_k(\seq{x}) = 0^{m_k}\} \right) \\
\findent \eqvar{(b)} \max_{P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}} \frac{1}{n_k} \ln \alpha(F_k)(P, P_{0^{m_k}}) \\
\findent \levar{(c)} \delta + \epsilon
\end{IEEEeqnarray*}
for sufficiently large $k$, where (a) follows from Proposition~\ref{pr:SpectrumProperty2UnderVectorPermutation}, (b) from Proposition~\ref{pr:SpectrumPropertyOfFunctions}, and (c) follows from \eqref{eq:ProofEq1OfRelationBetweenLSCCandLSCLCC}. Since $\epsilon$ is arbitrary, we conclude that $\seqx{F}$ is $\delta$-asymptotically SC-good.

Also by \eqref{eq:ProofEq1OfRelationBetweenLSCCandLSCLCC}, we have
\begin{IEEEeqnarray}{l}
E[S_{\mathcal{X}\mathcal{Y}}(F_k)(P, Q)] \le e^{n_k(\delta + \epsilon)} S_{\mathcal{X}\mathcal{Y}}(\mathcal{X}^{n_k} \times \mathcal{Y}^{m_k})(P, Q) \IEEEnonumber \\
\hspace{5em} \forall P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}, \forall Q \in \mathcal{P}_{m_k}(\mathcal{Y}) \label{eq:ProofEq2OfRelationBetweenLSCCandLSCLCC}
\end{IEEEeqnarray}
for sufficiently large $k$. Then for any $Q \in \mathcal{P}_{m_k}(\mathcal{Y}) \backslash \{P_{0^{m_k}}\}$, it follows that
\begin{IEEEeqnarray*}{l}
E[S_{\mathcal{Y}}(F_k(\mathcal{X}^{n_k}))(Q)] \\
\findent \eqvar{(a)} E[S_{\mathcal{Y}}(F_k)(Q)] \\
\findent = \sum_{P \in \mathcal{P}_{n_k}(\mathcal{X})} E[S_{\mathcal{X}\mathcal{Y}}(F_k)(P, Q)] \\
\findent \eqvar{(b)} \sum_{P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}} E[S_{\mathcal{X}\mathcal{Y}}(F_k)(P, Q)] \\
\findent \levar{(c)} \sum_{P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}} e^{n_k(\delta + \epsilon)} S_{\mathcal{X}\mathcal{Y}}(\mathcal{X}^{n_k} \times \mathcal{Y}^{m_k})(P, Q) \\
\findent \le e^{n_k(\delta + \epsilon)} S_{\mathcal{Y}}(\mathcal{Y}^{m_k})(Q)
\end{IEEEeqnarray*}
for sufficiently large $k$, where (a) follows from the property of linear codes, (b) from the condition $Q \ne P_{0^{m_k}}$, and (c) follows from \eqref{eq:ProofEq2OfRelationBetweenLSCCandLSCLCC}. Hence we have
\begin{IEEEeqnarray*}{l}
\limsup_{k \to \infty} \max_{Q \in \mathcal{P}_{m_k}(\mathcal{Y}) \backslash \{P_{0^{m_k}}\}} \frac{1}{m_k} \ln \alpha(F_k(\mathcal{X}^{n_k}))(Q) \\
\findent = \limsup_{k \to \infty} \max_{Q \in \mathcal{P}_{m_k}(\mathcal{Y}) \backslash \{P_{0^{m_k}}\}} \frac{1}{m_k} \ln \frac{E[S_{\mathcal{Y}}(F_k(\mathcal{X}^{m_k}))(Q)]}{S_{\mathcal{Y}}(\mathcal{Y}^{m_k})(Q)} \\
\findent \le \limsup_{k \to \infty} \frac{1}{m_k} \ln e^{n_k(\delta + \epsilon)} \\
\findent = (\delta + \epsilon) \overline{R}(\seqx{F}).
\end{IEEEeqnarray*}
Because $\epsilon$ is arbitrary, $\seqx{F}$ is $\delta\overline{R}(\seqx{F})$-asymptotically CC-good.
\end{proofof}

\begin{proofof}{Proposition~\ref{pr:DiagonalArgument}}
Note that
\[
\limsup_{k \to \infty} \rho(G_{k,k}) \le \limsup_{k \to \infty} \rho(G_{i,k}) \le \delta_i, \quad \forall i \in \pintegers
\]
and hence $\limsup_{k \to \infty} \rho(G_{k,k}) \le \inf_{i \in \pintegers} \delta_i = \delta$.
\end{proofof}



\subsection{Proofs of Results in Section \ref{subsec:MRDLSCC}}\label{subsec:ProofOfMRDLSCC}

\begin{proofof}{Proposition \ref{pr:MRDLSCC}}
We may assume $n\geq m$ and $\mathcal{C}=\mathcal{C}_k$ for some $1\leq k\leq m$. Since $x_1,\dots,x_m$ can be extended to a basis $x_1,\dots,x_n$ of $\field{q^n}$ over $\field{q}$, the code $\mathcal{C}_k\subseteq\field{q}^{n\times m}$ is obtained by projection from a corresponding code $\mathcal{C}_k'\subseteq\field{q}^{n\times n}$. Since the corresponding properties of $\mathcal{C}_k'$ clearly imply those of $\mathcal{C}_k$, it suffices to consider the ``square case'' $m=n$. Since $\mathcal{C}_1\subset\mathcal{C}_2\subset\dots\subset \mathcal{C}_n$, we may further restrict attention to the $(n,n,n)$ MRD code $\mathcal{C}_1$.

In this case, since $|\mathcal{C}_1|=q^n$, it suffices to show that the maps $\mathcal{C}_1\to\field{q}^n$, $\mat{A}\mapsto\seq{x}\mat{A}$ and $\mat{A}\mapsto\mat{A}\seq{y}^T$ are one-to-one. Now $\seq{x}\mat{A}=\seq{x}\mat{B}$ ($\mat{A},\mat{B}\in\mathcal{C}_1$) implies $\seq{x}(\mat{A}-\mat{B})=0^n$ and hence $\rank{\mat{A}-\mat{B}}<n$. Since $\mathcal{C}_1$ has minimum rank distance $n$, this implies $\mat{A}=\mat{B}$, proving the claim. The case of $\mat{A}\mapsto\mat{A}\seq{y}^T$ is done in the same way.
\end{proofof}

\begin{proofof}{Theorem \ref{th:MRDLSCC}}
We shall show $P\{F(\seq{x})=\seq{y}\}=q^{-m}$ for all $\seq{x}\in\field{q}^n\setminus\{0^n\}$ and $\seq{y}\in\field{q}^m$; equivalently, for fixed $\seq{x}\in\field{q}^n\setminus\{0^n\}$ the number $P\{F(\seq{x})=\seq{y}\}$ is independent of $\seq{y}$. By definition of $F$,
\begin{equation*}
  P\{F(\seq{x})=\seq{y}\}=\frac{\left|\{\mat{A}\in\mathcal{C} |
    \seq{x}\mat{A}=\seq{y}\}\right|}{|\mathcal{C}|}.
\end{equation*}
By Proposition~\ref{pr:MRDLSCC} the linear map $\mathcal{C}\to\field{q}^m$, $\mat{A}\mapsto\seq{x}\mat{A}$ is surjective. This implies that $\left|\{\mat{A}\in C| \seq{x}\mat{A}=\seq{y}\}\right|$ is equal to the cardinality of the kernel $\{\mat{A}\in C| \seq{x}\mat{A}=0^m\}$ and hence independent of $\seq{y}$.
\end{proofof}


\subsection{Proofs of Results in Section \ref{subsec:ConstructingGoodLSCCGPA}}\label{subsec:ProofOfConstructingGoodLSCCGPA}

\begin{proofof}{Theorem \ref{th:elementary_abelian}}
Condition \eqref{eq:SuperGoodLinearCodes2} implies that for every pair $\seq{x}\in\mathcal{X}^n\setminus\{0^n\}$, $\seq{y}\in\mathcal{Y}^m$ there exists at least one linear code $f:\mathcal{X}^n\to\mathcal{Y}^m$ satisfying $f(\seq{x})=\seq{y}$.\footnote{The existence of such an $f$ depends only on the types of $\seq{x}$ and $\seq{y}$, since $f$ is linear iff $\sigma\circ f\circ\pi$ is linear for any permutations $\pi \in \symmetricgroup{n}$, $\sigma \in \symmetricgroup{m}$.} Since $m,n\geq 1$, this in turn implies, for every pair $x\in\mathcal{X}\setminus\{0\}$, $y\in\mathcal{Y}$, the existence of at least one group homomorphism $h:\mathcal{X}\to\mathcal{Y}$ satisfying $h(x)=y$. (In fact the abelian group $\mathrm{Hom}(\mathcal{X}^n,\mathcal{Y}^m)$ of all group homomorphisms from $\mathcal{X}^n$ to $\mathcal{Y}^m$ is isomorphic to the group of all $m\times n$ matrices over the abelian group $H:=\mathrm{Hom}(\mathcal{X},\mathcal{Y})$ and the order of $H$ can be computed from the structures of $\mathcal{X}$ and $\mathcal{Y}$.)

If $p$ is a prime dividing $|\mathcal{X}|$, there exists $x\in\mathcal{X}$ of order $p$. Then, by the condition above, every $y\in\mathcal{Y}$ must have order $1$ or $p$, so $\mathcal{Y}\cong\integers_p^s$ for some $s$. If $|\mathcal{X}|$ has a prime divisor $q\neq p$, then $\mathcal{Y}\cong\integers_p^s\cong\integers_q^t$ and so $|\mathcal{Y}|=1$, a contradiction. Thus, $\mathcal{X}$ and $\mathcal{Y}$ must be $p$-groups for the same prime $p$, and $\mathcal{Y}$ must be elementary abelian. Finally, if $\mathcal{X}$ contains an element of order $p^2$ and $h:\mathcal{X}\to\mathcal{Y}$ is any group homomorphism, we have $px\neq 0$ but $h(px)=ph(x)=0$. This implies again $|\mathcal{Y}|=1$ and concludes the proof.
\end{proofof}

To prove Theorem~\ref{th:KernelOfSuperGoodLinearCodes}, we need the following lemma.

\begin{lemma}\label{le:KernelOfSuperGoodLinearCodes1}
Let $F: \mathcal{X}^n \to \mathcal{Y}^m$ be a random linear code. If $F$ is SCC-good, then
\begin{equation}
E[|\ker F|] = 1 + |\mathcal{Y}|^{-m} (|\mathcal{X}|^n - 1).
\end{equation}
\end{lemma}

\begin{proof}
\begin{IEEEeqnarray*}{rCl}
E[|\ker F|]
&= &E[|\ker \tilde{F}|] \\
&= &E\left[\sum_{\seq{x} \in \mathcal{X}^n} 1\{\tilde{F}(\seq{x}) = 0^m\}\right] \\
&= &1 + \sum_{\seq{x} \in \mathcal{X}^n \backslash \{0^n\}} P\{\tilde{F}(\seq{x}) = 0^m\} \\
&\eqvar{(a)} &1 + |\mathcal{Y}|^{-m} (|\mathcal{X}|^n - 1)
\end{IEEEeqnarray*}
where (a) follows from \eqref{eq:SuperGoodLinearCodes2}.
\end{proof}

\begin{proofof}{Theorem \ref{th:KernelOfSuperGoodLinearCodes}}
By Lagrange's theorem, $|\ker F|$ can take only values in $\{1,p,\dots,p^{rn}\}$. Hence, using Lemma~\ref{le:KernelOfSuperGoodLinearCodes1}, we obtain
\begin{IEEEeqnarray*}{rCl}
  1+\frac{q^n-1}{q^n} &= &E[|\ker F|] \\
  &\geq &P\{|\ker F|=1\}+p\cdot\left(1-P\{|\ker F|=1\}\right).
\end{IEEEeqnarray*}
Solving for $P\{|\ker F|=1\}$ gives the stated inequality.
\end{proofof}

\begin{proofof}{Proposition~\ref{pr:KernelOfSuperGoodLinearCodes}}
Suppose $\mathcal{X}\cong\integers_2^s$, so that $\mathcal{X}^n\cong\integers_2^{ns}\cong(\field{2}^{ns},+)$ for all $n\in\pintegers$.  Let $F_n:\field{2}^{ns}\to\field{2}^{ns}$ be the random linear code derived from a binary $(ns,ns,2)$ Gabidulin MRD code $\mathcal{C}$ in accordance with Theorem~\ref{th:MRDLSCC}. By definition, the code $\mathcal{C}$ consists of $2^{2ns}$ matrices $\mat{A}\in\field{2}^{ns\times ns}$ with $\rank{\mat{A}}\in\{ns-1,ns\}$ and hence $|\ker\mat{A}|\in\{1,2\}$. For $F_n$ this means that equality holds in the bound of Theorem~\ref{th:KernelOfSuperGoodLinearCodes}, and we get
\begin{IEEEeqnarray*}{l}
  \lim_{n\to\infty}P\{|\ker F_n|=1\}
  =\lim_{n\to\infty}\frac{2-2+2^{-ns}}{2-1}=0.
\end{IEEEeqnarray*}
Since $F_n$ is SCC-good (see Theorem~\ref{th:MRDLSCC}), this proves the proposition.
\end{proofof}

\begin{proofof}{Theorem \ref{th:ConstructionOfEquivalentCodes}}
The inequalities \eqref{eq:SCEquivalentProbability} and \eqref{eq:CCEquivalentProbability} are easy consequences of Theorem~\ref{th:RankOfRLC}. Next, let us evaluate the average conditional spectra of $G_1$ and $G_2$.

For any $P \in \mathcal{P}_n(\mathcal{X}) \backslash \{P_{0^n}\}$ and $Q \in \mathcal{P}_m(\mathcal{Y})$,
\begin{IEEEeqnarray*}{l}
E[S_{\mathcal{Y}|\mathcal{X}}(G_1)(Q|P)] \\
\findent \eqvar{(a)} \sum_{O \in \mathcal{P}_m(\mathcal{Y})} E[S_{\mathcal{Y}|\mathcal{X}}(F)(O|P)] E[S_{\mathcal{Y}|\mathcal{Y}}(\rlccode{q,m,m})(Q|O)] \\
\findent \eqvar{(b)} 1\{Q \ne P_{0^m}\} E[S_{\mathcal{Y}}(\mathcal{Y}^n)(Q)] \\
\findent \nullrel \breakop{\times} \sum_{O \in \mathcal{P}_m(\mathcal{Y}) \backslash P_{0^{m}}} E[S_{\mathcal{Y}|\mathcal{X}}(F)(O|P)] \\
\findent \nullrel \breakop{+} 1\{Q = P_{0^m}\} \Bigg( E[S_{\mathcal{Y}|\mathcal{X}}(F)(P_{0^m}|P)] \\
\findent \nullrel \breakop{+} E[S_{\mathcal{Y}}(\mathcal{Y}^n)(Q)] \sum_{O \in \mathcal{P}_m(\mathcal{Y}) \backslash P_{0^{m}}} E[S_{\mathcal{Y}|\mathcal{X}}(F)(O|P)] \Bigg) \\
\findent = E[S_{\mathcal{Y}}(\mathcal{Y}^n)(Q)] \sum_{O \in \mathcal{P}_m(\mathcal{Y}) \backslash P_{0^{m}}} E[S_{\mathcal{Y}|\mathcal{X}}(F)(O|P)] \\
\findent \nullrel \breakop{+} 1\{Q = P_{0^m}\} E[S_{\mathcal{Y}|\mathcal{X}}(F)(P_{0^m}|P)] \\
\findent \le E[S_{\mathcal{Y}}(\mathcal{Y}^n)(Q)] + 1\{Q = P_{0^m}\} E[S_{\mathcal{Y}|\mathcal{X}}(F)(P_{0^m}|P)]
\end{IEEEeqnarray*}
where (a) follows from Proposition~\ref{pr:SpectrumOfSeriallyConcatenatedFunctions} and (b) follows from \eqref{eq:SuperGoodLinearCodes1}. This concludes \eqref{eq:SCEquivalentCodeSpectrum}.

Analogously, for any $P \in \mathcal{P}_n(\mathcal{X}) \backslash \{P_{0^n}\}$ and $Q \in \mathcal{P}_m(\mathcal{Y})$,
\begin{IEEEeqnarray*}{l}
E[S_{\mathcal{Y}|\mathcal{X}}(G_2)(Q|P)] \\
\findent \eqvar{(a)} \sum_{O \in \mathcal{P}_n(\mathcal{X})} E[S_{\mathcal{X}|\mathcal{X}}(\rlccode{q,n,n})(O|P)] E[S_{\mathcal{Y}|\mathcal{X}}(F)(Q|O)] \\
\findent \eqvar{(b)} \sum_{O \in \mathcal{P}_n(\mathcal{X})} E[S_{\mathcal{X}}(\mathcal{X}^n)(O)] E[S_{\mathcal{Y}|\mathcal{X}}(F)(Q|O)] \\
\findent = \sum_{O \in \mathcal{P}_n(\mathcal{X})} E[S_{\mathcal{X}\mathcal{Y}}(F)(O,Q)] \\
\findent = E[S_{\mathcal{Y}}(F)(Q)] \\
\findent = E[S_{\mathcal{Y}}(F(\mathcal{X}^n))(Q)]
\end{IEEEeqnarray*}
where (a) follows from Proposition~\ref{pr:SpectrumOfSeriallyConcatenatedFunctions} and (b) follows from \eqref{eq:SuperGoodLinearCodes1}. This concludes \eqref{eq:CCEquivalentCodeSpectrum} and hence completes the proof.
\end{proofof}

\begin{proofof}{Theorem \ref{th:ConstructionOfGoodEquivalentCodes}}
For the first statement, recall that the source transmission rate of $\delta$-asymptotically good LSCs must converges. Then for any $\epsilon>0$, since $\seqx{f}$ is asymptotically SC-good and satisfies \eqref{eq:ConstructionOfGoodEquivalentCodes}, we have
\begin{equation}\label{eq:ProofEq1OfConstructionOfGoodEquivalentCodes}
\alpha(\ker f_k)(P) \le e^{n_k(\delta + \epsilon)} \qquad \forall P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}
\end{equation}
and
\begin{equation}\label{eq:ProofEq2OfConstructionOfGoodEquivalentCodes}
|f_k(\mathcal{X}^{n_k})| \ge |\mathcal{Y}|^{m_k} e^{-m_k \epsilon} \ge |\mathcal{Y}|^{m_k} e^{-2n_k\epsilon/R(\seqx{f})}
\end{equation}
for sufficiently large $k$. Because $\mathcal{Y}$ is elementary abelian, we define the random linear code $G_{1,k} \eqdef \rlccode{q,m_k,m_k} \circ f_k$, where $q = |\mathcal{Y}|$. It follows from Theorem~\ref{th:ConstructionOfEquivalentCodes} that
\begin{equation}\label{eq:ProofEq3OfConstructionOfGoodEquivalentCodes}
\inf_{k \in \pintegers} P\{\ker G_{1,k} = \ker f_k\} > K_q
\end{equation}
and
\begin{IEEEeqnarray*}{l}
E[S_{\mathcal{Y}|\mathcal{X}}(G_{1,k})(Q|P)] \\
\findent \le S_{\mathcal{Y}}(\mathcal{Y}^{m_k})(Q) + 1\{Q = P_{0^{m_k}}\} S_{\mathcal{Y}|\mathcal{X}}(f_k)(P_{0^{m_k}}|P) \\
\hspace{5em} \forall P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}, \forall Q \in \mathcal{P}_{m_k}(\mathcal{Y}).
\end{IEEEeqnarray*}
Hence for any $P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}$ and any $Q \in \mathcal{P}_{m_k}(\mathcal{Y})$,
\begin{IEEEeqnarray*}{l}
\alpha(G_{1,k})(P, Q) \\
\findent = \frac{E[S_{\mathcal{Y}|\mathcal{X}}(G_{1,k})(Q|P)]}{S_{\mathcal{Y}}(\mathcal{Y}^{m_k})(Q)} \\
\findent \le 1 + 1\{Q = P_{0^{m_k}}\} \alpha(f_k)(P, P_{0^{m_k}}) \\
\findent \eqvar{(a)} 1 + 1\{Q = P_{0^{m_k}}\} |\mathcal{Y}|^{m_k} P\{\rtilde{f}_k(\seq{x}) = 0^{m_k}\} \\
\findent = 1 + 1\{Q = P_{0^{m_k}}\} |\mathcal{Y}|^{m_k} P\{\seq{x} \in \widetilde{\ker f_k}\} \\
\findent \eqvar{(b)} 1 + 1\{Q = P_{0^{m_k}}\} |\mathcal{Y}|^{m_k} \frac{|\ker f_k|}{|\mathcal{X}|^{n_k}} \alpha(\ker f_k)(P) \\
\findent = 1 + 1\{Q = P_{0^{m_k}}\} \frac{|\mathcal{Y}|^{m_k}}{|f_k(\mathcal{X}^{n_k})|} \alpha(\ker f_k)(P) \\
\findent \levar{(c)} 1 + 1\{Q = P_{0^{m_k}}\} e^{2n_k\epsilon/R(\seqx{f})} \alpha(\ker f_k)(P) \\
\findent \levar{(d)} e^{n_k(\delta + 2\epsilon + 2\epsilon/R(\seqx{f}))}
\end{IEEEeqnarray*}
for sufficiently large $k$, where (a) follows from Proposition~\ref{pr:SpectrumPropertyOfFunctions} and $\seq{x}$ is some sequence of type $P$, (b) from Proposition~\ref{pr:SpectrumProperty2UnderVectorPermutation}, (c) from \eqref{eq:ProofEq2OfConstructionOfGoodEquivalentCodes}, and (d) follows from \eqref{eq:ProofEq1OfConstructionOfGoodEquivalentCodes}. Thus for sufficiently large $k$,
$$
\rho(G_{1,k}) \le \delta + 2\epsilon + \frac{2\epsilon}{R(\seqx{f})}.
$$
Define the new random linear code $G_{1,k}'$ as $G_{1,k}$ conditioned on the event $A_k \eqdef \{\ker G_{1,k} = \ker f_k\}$ (i.e., an expurgated ensemble). Then it follows that for sufficiently large $k$,
\begin{IEEEeqnarray*}{rCl}
\rho(G_{1,k}')
&\le &\rho(G_{1,k}) - \frac{1}{n_k} \ln P(A_k) \\
&\le &\delta + 2\epsilon + \frac{2\epsilon}{R(\seqx{f})} - \frac{1}{n_k} \ln P(A_k) \\
&\levar{(a)} &\delta + 3\epsilon + \frac{2\epsilon}{R(\seqx{f})}
\end{IEEEeqnarray*}
where (a) follows from \eqref{eq:ProofEq3OfConstructionOfGoodEquivalentCodes}. Since $\epsilon$ is arbitrary, $\{G_{1,k}'\}_{k=1}^\infty$ is a sequence of $\delta$-asymptotically good LSCCs such that $\ker G_{1,k}' = \ker f_k$. By Proposition 4.1 in \cite{JSCC:Yang200904}, we conclude that there exists a sequence $\{g_{1,k}\}_{k=1}^\infty$ of $\delta$-asymptotically good LSCCs $g_{1,k}: \mathcal{X}^{n_k} \to \mathcal{Y}^{m_k}$ such that $g_{1,k}$ is SC-equivalent to $f_k$ for each $k \in \pintegers$.

The proof of the second statement is analogous. Let $\epsilon > 0$ be given. Since $\seqx{f}$ is $\delta$-asymptotically CC-good, we have
\begin{equation}\label{eq:ProofEq4OfConstructionOfGoodEquivalentCodes}
\alpha(f_k(\mathcal{X}^{n_k}))(Q) \le e^{m_k(\delta + \epsilon)} \qquad \forall Q \in \mathcal{P}_{m_k}(\mathcal{Y}) \backslash \{P_{0^{m_k}}\}
\end{equation}
for sufficiently large $k$. Noting that $\mathcal{X}$ is elementary abelian, we define the random linear code $G_{2,k} \eqdef f_k \circ \rlccode{q,n_k,n_k}$, where $q = |\mathcal{X}|$. Then it follows from Theorem~\ref{th:ConstructionOfEquivalentCodes} that
\begin{equation}\label{eq:ProofEq5OfConstructionOfGoodEquivalentCodes}
\inf_{k \in \pintegers} P\{G_{2,k}(\mathcal{X}^{n_k}) = f_k(\mathcal{X}^{n_k})\} > K_q
\end{equation}
and
\begin{IEEEeqnarray*}{l}
E[S_{\mathcal{Y}|\mathcal{X}}(G_{2,k})(Q|P)] = S_{\mathcal{Y}}(f_k(\mathcal{X}^{n_k}))(Q) \\
\hspace{5em} \forall P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}, \forall Q \in \mathcal{P}_{m_k}(\mathcal{Y}).
\end{IEEEeqnarray*}
Hence for any $P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}$ and any $Q \in \mathcal{P}_{m_k}(\mathcal{Y})$,
\begin{IEEEeqnarray*}{rCl}
\alpha(G_{2,k})(P, Q)
&= &\frac{E[S_{\mathcal{Y}|\mathcal{X}}(G_{2,k})(Q|P)]}{S_{\mathcal{Y}}(\mathcal{Y}^{m_k})(Q)} \\
&= &\frac{S_{\mathcal{Y}}(f_k(\mathcal{X}^{n_k}))(Q)}{S_{\mathcal{Y}}(\mathcal{Y}^{m_k})(Q)} \\
&= &\alpha(f_k(\mathcal{X}^{n_k}))(Q)
\end{IEEEeqnarray*}
for sufficiently large $k$. Define the new random linear code $G_{2,k}'$ as $G_{2,k}$ conditioned on the event $B_k \eqdef \{G_{2,k}(\mathcal{X}^{n_k}) = f_k(\mathcal{X}^{n_k})\}$. Then it follows that for any $P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}$ and any $Q \in \mathcal{P}_{m_k}(\mathcal{Y}) \backslash \{P_{0^{m_k}}\}$,
$$
\alpha(G_{2,k}')(P, Q) \le \frac{\alpha(f(\mathcal{X}^{n_k}))(Q)}{P(B_k)} \levar{(a)} e^{m_k(\delta + 2\epsilon)}
$$
for sufficiently large $k$, where (a) follows from \eqref{eq:ProofEq4OfConstructionOfGoodEquivalentCodes} and \eqref{eq:ProofEq5OfConstructionOfGoodEquivalentCodes}. Since $f_k$ is injective, we have
$$
\alpha(G_{2,k}')(P, P_{0^{m_k}}) = 0 \qquad \forall P \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}
$$
and
$$
R(f_k) = \frac{R_c(f_k)}{\ln |\mathcal{X}|}
$$
converges as $k \to \infty$. Therefore, we have
$$
\rho(G_{2,k}') \le \frac{\delta + 2\epsilon}{R(\seqx{f})} + \epsilon
$$
for sufficiently large $k$. Since $\epsilon$ is arbitrary, $\{G_{2,k}'\}_{k=1}^\infty$ is a sequence of $\delta/R(\seqx{f})$-asymptotically good LSCCs such that $G_{2,k}'(\mathcal{X}^{n_k}) = f_k(\mathcal{X}^{n_k})$. By Proposition 4.1 in \cite{JSCC:Yang200904}, we conclude that there exists a sequence $\{g_{2,k}\}_{k=1}^\infty$ of $\delta/R(\seqx{f})$-asymptotically good LSCCs $g_{2,k}: \mathcal{X}^{n_k} \to \mathcal{Y}^{m_k}$ such that $g_{2,k}$ is CC-equivalent to $f_k$ for each $k \in \pintegers$.
\end{proofof}


\subsection{Proofs of Results in Section \ref{subsec:ConstructingGoodLSCCGPB}}\label{subsec:ProofOfConstructingGoodLSCCGPB}

\begin{proofof}{Theorem \ref{th:ConstructionOfGoodLSCC}}
Let $\epsilon > 0$ be given. Since $G_k$ is $\delta$-asymptotically SCC-good relative to $A_k$, we have
\begin{IEEEeqnarray}{l}
E[S_{\mathcal{Z}|\mathcal{Y}}(G_k)(Q|P)] \le e^{m_k(\delta + \epsilon)} S_{\mathcal{Z}}(\mathcal{Z}^{l_k})(Q) \IEEEnonumber \\
\hspace{8em} \forall P \in A_k, Q \in P_{l_k}(\mathcal{Z}).\label{eq:ConstructionOfGoodLSCCEq1}
\end{IEEEeqnarray}
for sufficiently large $k$. Then for all $O \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}$ and $Q \in P_{l_k}(\mathcal{Z})$,
\begin{IEEEeqnarray*}{l}
S_{\mathcal{Z}|\mathcal{X}}(G_k \circ \Sigma_{m_k} \circ F_k)(Q|O) \\
\findent \eqvar{(a)} \sum_{P \in \mathcal{P}_{m_k}(\mathcal{Y})} E[S_{\mathcal{Y}|\mathcal{X}}(F_k)(P|O)] E[S_{\mathcal{Z}|\mathcal{Y}}(G_k)(Q|P)] \\
\findent \eqvar{(b)} \sum_{P \in A_k} E[S_{\mathcal{Y}|\mathcal{X}}(F_k)(P|O)] E[S_{\mathcal{Z}|\mathcal{Y}}(G_k)(Q|P)] \\
\findent \levar{(c)} \sum_{P \in A_k} e^{m_k(\delta + \epsilon)} S_{\mathcal{Z}}(\mathcal{Z}^{l_k})(Q) E[S_{\mathcal{Y}|\mathcal{X}}(F_k)(P|O)] \\
\findent \le e^{m_k(\delta + \epsilon)} S_{\mathcal{Z}}(\mathcal{Z}^{l_k})(Q)
\end{IEEEeqnarray*}
for sufficiently large $k$, where (a) follows from Proposition~\ref{pr:SpectrumOfSeriallyConcatenatedFunctions}, (b) from the condition \eqref{eq:ConstructionOfGoodLSCC1}, and (c) follows from \eqref{eq:ConstructionOfGoodLSCCEq1}. Therefore, for sufficiently large $k$,
$$
\rho(G_k \circ \Sigma_{m_k} \circ F_k) \le \frac{\delta + \epsilon}{\underline{R}(\seqx{F})} + \epsilon.
$$
Since $\epsilon$ is arbitrary, this establishes the theorem.
\end{proofof}

\begin{proofof}{Proposition \ref{pr:ConstructionOfGoodLSCCbySurjectiveMapping}}
For any $\epsilon > 0$, since $F_k$ is $\delta$-asymptotically SCC-good, we have
\begin{IEEEeqnarray}{l}
E[S_{\mathcal{Y}|\mathcal{X}}(F_k)(P|O)] \le e^{n_k(\delta + \epsilon)} S_{\mathcal{Y}}(\mathcal{Y}^{m_k})(P) \IEEEnonumber \\
\hspace{4em} \forall O \in P_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}, P \in P_{m_k}(\mathcal{Y}).\label{eq:ConstructionOfGoodLSCCbySurjectiveMappingEq1}
\end{IEEEeqnarray}
for sufficiently large $k$. Then for all $O \in \mathcal{P}_{n_k}(\mathcal{X}) \backslash \{P_{0^{n_k}}\}$ and $Q \in P_{l_k}(\mathcal{Z})$,
\begin{IEEEeqnarray*}{l}
S_{\mathcal{Z}|\mathcal{X}}(G_k \circ \Sigma_{m_k} \circ F_k)(Q|O) \\
\findent \eqvar{(a)} \sum_{P \in \mathcal{P}_{m_k}(\mathcal{Y})} E[S_{\mathcal{Y}|\mathcal{X}}(F_k)(P|O)] E[S_{\mathcal{Z}|\mathcal{Y}}(G_k)(Q|P)] \\
\findent \levar{(b)} \sum_{P \in \mathcal{P}_{m_k}(\mathcal{Y})} e^{n_k(\delta + \epsilon)} S_{\mathcal{Y}}(\mathcal{Y}^{m_k})(P) E[S_{\mathcal{Z}|\mathcal{Y}}(G_k)(Q|P)] \\
\findent = e^{n_k(\delta + \epsilon)} \sum_{P \in \mathcal{P}_{m_k}(\mathcal{Y})} E[S_{\mathcal{Y}\mathcal{Z}}(G_k)(P,Q)] \\
\findent = e^{n_k(\delta + \epsilon)} S_{\mathcal{Z}}(G_k)(Q) \\
\findent = e^{n_k(\delta + \epsilon)} S_{\mathcal{Z}}(G_k(\mathcal{Y}^{m_k}))(Q) \\
\findent \eqvar{(c)} e^{n_k(\delta + \epsilon)} S_{\mathcal{Z}}(\mathcal{Z}^{l_k})(Q)
\end{IEEEeqnarray*}
for sufficiently large $k$, where (a) follows from Proposition~\ref{pr:SpectrumOfSeriallyConcatenatedFunctions}, (b) from \eqref{eq:ConstructionOfGoodLSCCbySurjectiveMappingEq1}, and (c) follows from the surjective property of $G_k$. Therefore, for sufficiently large $k$,
$$
\rho(G_k \circ \Sigma_{m_k} \circ F_k) \le \delta + \epsilon.
$$
This concludes the proof, because $\epsilon$ is arbitrary.
\end{proofof}


\subsection{Proofs of Results in Section \ref{sec:ExplicitConstruction}}\label{subsec:ProofOfExplicitConstruction}

\begin{proofof}{Proposition \ref{pr:SpectrumOfREPCode}}
The identity \eqref{eq:SpectrumOfREPCodeA1} holds clearly. This together with Propositions~\ref{pr:RenameGeneratingFunction} gives the identity \eqref{eq:SpectrumOfREPCodeA2}.

From \eqref{eq:SpectrumOfREPCodeA1} and Corollary~\ref{co:GeneratingFunctionOfFunctionParallelProduct}, it further follows that
\begin{IEEEeqnarray*}{rCl}
\mathcal{G}(\repcode{q,c,n})(\seq{u}, \seq{v})
&= &\left( \frac{1}{q} \sum_{a \in \field{q}} u_a v_a^c \right)^n \\
&= &\frac{1}{q^n} \sum_{P \in \mathcal{P}_n(\field{q})} {n \choose nP} \seq{u}^{nP} \seq{v}^{ncP} \\
&= &\sum_{P \in \mathcal{P}_n(\field{q})} S(\field{q}^n)(P) \seq{u}^{nP} \seq{v}^{ncP}.
\end{IEEEeqnarray*}
This proves \eqref{eq:SpectrumOfREPCodeB}. The identities \eqref{eq:SpectrumOfREPCodeC} and \eqref{eq:SpectrumOfREPCodeD} are easy consequences of \eqref{eq:SpectrumOfREPCodeB}.
\end{proofof}

\begin{proofof}{Proposition \ref{pr:SpectrumOfCHKCode}}
Note that the generator matrix of $\rchkcode{q,d}$ is the transpose of the generator matrix of $\rrepcode{q,d}$. Then by Theorem~\ref{th:MacWilliamsIdentitiesJF}, it follows that
\begin{IEEEeqnarray*}{l}
E[\mathcal{G}(-\rchkcode{q,d})(\seq{u}, \seq{v})] \\
\findent = \frac{1}{q^d} E[\mathcal{G}(\rrepcode{q,d})(\hat{\seq{v}}, \hat{\seq{u}})] \\
\findent \eqvar{(a)} \frac{1}{q^{d+1}} \left[ \hat{u}_0^d \hat{v}_0 + \left( \frac{(\hat{\seq{u}})_\oplus - \hat{u}_0}{q-1} \right)^d ((\hat{\seq{v}})_\oplus - \hat{v}_0) \right] \\
\findent \eqvar{(b)} \frac{1}{q^{d+1}} \left[ ((\seq{u})_\oplus)^d (\seq{v})_\oplus + \left( \frac{qu_0 - (\seq{u})_\oplus}{q-1} \right)^d (qv_0 - (\seq{v})_\oplus) \right]
\end{IEEEeqnarray*}
where $\hat{\seq{u}} = \seq{u} \mat{M}$ and $\hat{\seq{v}} = \seq{v} \mat{M}$, (a) follows from Proposition~\ref{pr:SpectrumOfREPCode}, and (b) follows from the property \eqref{eq:MacWilliamsMatrixPropertyF}. This together with Proposition~\ref{pr:RenameGeneratingFunction} concludes the identity \eqref{eq:SpectrumOfCHKCodeA}.

By Corollary~\ref{co:GeneratingFunctionOfFunctionParallelProduct}, we further have
\begin{IEEEeqnarray*}{l}
E[\mathcal{G}(\rchkcode{q,d,n})(\seq{u}, \seq{v})] \\
\findent = \frac{1}{q^{n(d+1)}} \Bigg[ ((\seq{u})_\oplus)^d (\seq{v})_\oplus \\
\findent \nullrel \breakop{+} \left( \frac{qu_0 - (\seq{u})_\oplus}{q-1} \right)^d (qv_0 - (\seq{v})_\oplus) \Bigg]^n \\
\findent = \frac{1}{q^{n(d+1)}} \Bigg\{ \left[ ((\seq{u})_\oplus)^d + (q-1)\left( \frac{qu_0 - (\seq{u})_\oplus}{q-1} \right)^d \right] v_0 \\
\findent \nullrel \breakop{+} \left[ ((\seq{u})_\oplus)^d - \left( \frac{qu_0 - (\seq{u})_\oplus}{q-1} \right)^d \right] ((\seq{v})_\oplus - v_0) \Bigg\}^n \\
\findent = \frac{1}{q^{n(d+1)}} \sum_{Q \in \mathcal{P}_{n}(\field{q})} \Bigg\{ {n \choose nQ} \seq{v}^{nQ} \\
\findent \nullrel \breakop{\times} \left[ ((\seq{u})_\oplus)^d + (q-1)\left( \frac{qu_0 - (\seq{u})_\oplus}{q-1} \right)^d \right]^{nQ(0)} \\
\findent \nullrel \breakop{\times} \left[ ((\seq{u})_\oplus)^d - \left( \frac{qu_0 - (\seq{u})_\oplus}{q-1} \right)^d \right]^{n(1-Q(0))} \Bigg\}.
\end{IEEEeqnarray*}
Hence,
\begin{IEEEeqnarray*}{rCl}
E[S(\rchkcode{q,d,n})(P,Q)]
&= &\coef{E[\mathcal{G}(\rchkcode{q,d,n})(\seq{u}, \seq{v})], \seq{u}^{dnP} \seq{v}^{nQ}} \\
&= &\coef{g_{q,d,n}^{(1)}(\seq{u}, Q), \seq{u}^{dnP}}
\end{IEEEeqnarray*}
where $g_{q,d,n}^{(1)}(\seq{u}, Q)$ is defined by \eqref{eq:DefinitionOfCHKCodeGF1}. This proves \eqref{eq:SpectrumOfCHKCodeB}.

Since $g_{q,d,n}^{(1)}(\seq{u}, Q)$ is a polynomial with nonnegative coefficients, $\coef{g_{q,d,n}^{(1)}(\seq{u}, Q), \seq{u}^{dnP}}$ can be bounded above by
\begin{IEEEeqnarray*}{rCl}
\coef{g_{q,d,n}^{(1)}(\seq{u}, Q), \seq{u}^{dnP}}
&\le &\frac{g_{q,d,n}^{(1)}(O, Q)}{O^{dnP}} \\
&= &g_{q,d,n}^{(2)}(O, P, Q)
\end{IEEEeqnarray*}
where $O$ is an arbitrary type in $\mathcal{P}_{dn}(\field{q})$ such that $O(a) > 0$ for all $a \in \{a|P(a) > 0\}$, and $g_{q,d,n}^{(2)}(O, P, Q)$ is defined dy \eqref{eq:DefinitionOfCHKCodeGF2}. This gives \eqref{eq:SpectrumOfCHKCodeC}.

Finally, let us estimate $\alpha(\rchkcode{q,d,n})(P, Q)$.
\begin{IEEEeqnarray*}{l}
\alpha(\rchkcode{q,d,n})(P, Q) \\
\findent \le \frac{g_{q,d,n}^{(2)}(O, P, Q)}{S(\field{q}^{dn} \times \field{q}^n)(P,Q)} \\
\findent = \frac{1}{{dn \choose dnP} O^{dnP}} \left[ 1 + (q - 1) \left( \frac{qO(0) - 1}{q-1} \right)^d \right]^{nQ(0)} \\
\findent \nullrel \breakop{\times} \left[ 1 - \left( \frac{qO(0) - 1}{q-1} \right)^d \right]^{n(1-Q(0))} \\
\findent = \frac{e^{dnH(P)} P^{dnP}}{{dn \choose dnP} O^{dnP}} \left[ 1 + (q - 1) \left( \frac{qO(0) - 1}{q-1} \right)^d \right]^{nQ(0)} \\
\findent \nullrel \breakop{\times} \left[ 1 - \left( \frac{qO(0) - 1}{q-1} \right)^d \right]^{n(1-Q(0))} \\
\findent = e^{dn\Delta_{q,dn}(P)} e^{dn D(P\|O)} \\
\findent \nullrel \breakop{\times} \left[ 1 + (q - 1) \left( \frac{qO(0) - 1}{q-1} \right)^d \right]^{nQ(0)} \\
\findent \nullrel \breakop{\times} \left[ 1 - \left( \frac{qO(0) - 1}{q-1} \right)^d \right]^{n(1-Q(0))}.
\end{IEEEeqnarray*}
Note that $D(P\|O) \ge D(P(0)\|O(0))$ with equality if and only if $P(a)(1-O(0)) = O(a)(1-P(0))$ for all $a \ne 0$, and thus we obtain a minimized upper bound \eqref{eq:SpectrumOfCHKCodeD}.
\end{proofof}

\begin{proofof}{Theorem \ref{th:SpectrumOfLDGMCode}}
By the definition of $\ldcode{q,c,d,n}$ and Proposition~\ref{pr:SpectrumOfSeriallyConcatenatedFunctions}, it follows that
\begin{IEEEeqnarray*}{l}
E[S(\ldcode{q,c,d,n})(Q|P)] \\
\findent = \sum_{O \in \mathcal{P}_{cd'n}(\field{q})} E[S(\repcode{q,c,d'n})(O|P)] E[S(\rchkcode{q,d,c'n})(Q|O)] \\
\findent \eqvar{(a)} \sum_{O \in \mathcal{P}_{cd'n}(\field{q})} 1\{O = P\} E[S(\rchkcode{q,d,c'n})(Q|O)] \\
\findent = E[S(\rchkcode{q,d,c'n})(Q|P)]
\end{IEEEeqnarray*}
where (a) follows from \eqref{eq:SpectrumOfREPCodeD}. This concludes \eqref{eq:SpectrumOfLDGMCodeA}.

Furthermore, we have
\begin{IEEEeqnarray*}{l}
\frac{1}{d'n} \ln \alpha(\ldcode{q,c,d,n})(P, Q) \\
\findent = \frac{1}{d'n} \ln \frac{E[S(\ldcode{q,c,d,n})(Q|P)]}{S(\field{q}^{c'n})(Q)} \\
\findent \eqvar{(a)} \frac{1}{d'n} \ln \frac{E[S(\rchkcode{q,d,c'n})(Q|P)]}{S(\field{q}^{c'n})(Q)} \\
\findent = \frac{1}{d'n} \ln \alpha(\rchkcode{q,d,c'n})(P, Q) \\
\findent \levar{(b)} \frac{c'}{d'} [\delta_{q,d}(P(0), Q(0)) + d \Delta_{q,c'dn}(P)] \\
\findent = \frac{c}{d} \delta_{q,d}(P(0), Q(0)) + c \Delta_{q,c'dn}(P)
\end{IEEEeqnarray*}
where (a) follows from \eqref{eq:SpectrumOfLDGMCodeA} and (b) follows from \eqref{eq:SpectrumOfCHKCodeD}. This concludes \eqref{eq:SpectrumOfLDGMCodeB} and hence completes the proof.
\end{proofof}

\begin{proofof}{Lemma \ref{le:UpperBoundOfDelta}}
When $x \in (0, 1)$ and $y \in [0, 1]$, the inequality \eqref{eq:UpperBoundOfDelta} clearly holds by taking $\hat{x} = x$ in \eqref{eq:DefinitionOfDelta}. If however $x = 0$, then
\begin{IEEEeqnarray*}{rCl}
\lim_{\hat{x} \to 0} \delta_{q,d}(0, \hat{x}, y) &= &\lim_{\hat{x} \to 0} \left( \ln \frac{1}{1-\hat{x}} + J_{q,d}(\hat{x},y) \right) \\
&= &J_{q,d}(0,y).
\end{IEEEeqnarray*}
Hence $\delta_{q,d}(0, y) \le J_{q,d}(0,y)$. Similar arguments also apply to the case of $x = 1$.
\end{proofof}

\begin{proofof}{Lemma \ref{le:UpperBoundOfJ}}
Apply Jensen's inequality.
\end{proofof}

\begin{proofof}{Theorem \ref{th:ApproximateSCCGoodLDGMCode}}
By Theorem~\ref{th:SpectrumOfLDGMCode}, Lemmas~\ref{le:UpperBoundOfDelta} and \ref{le:UpperBoundOfJ}, and the condition $r_0=d/c$, it follows that
\begin{IEEEeqnarray*}{l}
\frac{1}{d'n} \ln \alpha(\ldcode{q,c,d,n})(P,Q) \\
\findent \le \frac{1}{r_0} \ln\left[1+(qQ(0)-1) \left( \frac{qP(0)-1}{q-1} \right)^d\right] + c \Delta_{q,c'dn}(P) \\
\findent \levar{(a)} \frac{1}{r_0} \ln\left[1+(q-1)\left| \frac{qP(0)-1}{q-1} \right|^d\right] + \frac{q\ln(cd'n+1)}{d'n}
\end{IEEEeqnarray*}
where (a) follows from the strict increasing property of $\ln x$, $Q(0) \in [0,1]$, and the inequality
$$
{n \choose nP} \ge \frac{1}{(n+1)^q} e^{nH(P)} \quad \mbox{ (see \cite[Lemma~2.3]{JSCC:Csiszar198100})}.
$$
Note that
\[
\lim_{n \to \infty} \frac{q\ln(cd'n+1)}{d'n} = 0.
\]
All conclusions of the theorem follow immediately.
\end{proofof}

\begin{proofof}{Proposition \ref{pr:SingleCodeSpectrum}}
\begin{IEEEeqnarray*}{l}
\max_{\substack{P \in \mathcal{P}_n(\mathcal{X})\backslash \{P_{0^n}\}, \\ Q \in \mathcal{P}_m(\mathcal{Y})}} \alpha(f)(P,Q) \\
\findent \ge \max_{Q \in \mathcal{P}_m(\mathcal{Y})} \frac{S_{\mathcal{Y}|\mathcal{X}}(f)(Q|P_{a^n})}{S_{\mathcal{Y}}(\mathcal{Y}^m)(Q)} \\
\findent \ge \frac{\max_{Q \in \mathcal{P}_m(\mathcal{Y})} S_{\mathcal{Y}|\mathcal{X}}(f)(Q|P_{a^n})}{\max_{Q \in \mathcal{P}_m(\mathcal{Y})} S_{\mathcal{Y}}(\mathcal{Y}^m)(Q)} \\
\findent = \frac{|\mathcal{Y}|^m}{\max_{Q \in \mathcal{P}_m(\mathcal{Y})} {m \choose mQ}} \\
\findent \eqvar{(a)} \frac{|\mathcal{Y}|^m}{\order\left(m^{-\frac{|\mathcal{Y}|-1}{2}} |Y|^m\right)} \\
\findent = \order\left(m^{\frac{|\mathcal{Y}|-1}{2}}\right)
\end{IEEEeqnarray*}
where $a \ne 0$ and (a) follows from Stirling's approximation.
\end{proofof}


\section{Conclusion}\label{sec:Conclusion}

In this paper, we present some general principles and schemes for constructing linear codes with good joint spectra.

In Section~\ref{subsec:MRDLSCC}, we provide a family of SCC-good random linear codes which are derived from Gabibulin MRD codes. In Section~\ref{subsec:ConstructingGoodLSCCGPA}, it is proved in Theorem~\ref{th:ConstructionOfGoodEquivalentCodes} that, when the output (resp., input) alphabet is elementary abelian, we can construct $\delta$-asymptotically good LSCCs which are SC-equivalent (resp., CC-equivalent) to given $\delta$-asymptotically good LSCs (resp., LCCs). In Section~\ref{subsec:ConstructingGoodLSCCGPB}, we further propose a general serial concatenation scheme for constructing good LSCCs by Theorem~\ref{th:ConstructionOfGoodLSCC}. The interesting role of nonsingular rate-$1$ codes is also discussed in Corollary~\ref{co:ConstructionOfGoodLSCCbyInjectiveMapping} and Proposition~\ref{pr:ConstructionOfGoodLSCCbySurjectiveMapping}.

In Section~\ref{sec:ExplicitConstruction}, joint spectra of regular LDGM codes are analyzed. By Theorem~\ref{th:ApproximateSCCGoodLDGMCode}, we show that regular LDGM codes with appropriate parameters are approximately $\delta$-asymptotically SCC-good. Based on this analysis, we finally present a serial concatenation scheme with one LDPC code as outer code and one LDGM code as inner code, which is proved to be asymptotically SCC-good.

Besides the major contributions above, we also develop the code-spectrum approach and review in a uniform viewpoint the problems of constructing good linear codes for different applications. In Section~\ref{sec:NewMethodsAndResultsOfCodeSpectrum}, we establish a series of new concepts and results of code spectra, among which, spectrum generating functions, spectra with coordinate partitions, and the MacWilliams identities deserve much more attention. In Section~\ref{sec:ConceptsOfGoodLinearCodes}, we review the original requirements of good linear codes for lossless source coding, channel coding, and lossless JSCC, respectively. The code-spectrum criteria of good linear codes for different applications are then presented. Hence, all the coding issues are put into one common topic: constructing linear codes with good spectra. By investigating the relations among these criteria, we realize that a good joint spectrum is the most important feature of a linear code.


\section*{Acknowledgement}

The authors would like to thank the anonymous reviewers and the associate editor for their helpful comments.


\bibliographystyle{IEEEtranS} % use IEEEtran.bst style
\bibliography{IEEEabrv,JSCC3}

\end{document}

JSCC3.bbl
% Generated by IEEEtranS.bst, version: 1.13 (2008/09/30)
\begin{thebibliography}{10}
\providecommand{\url}[1]{#1}
\csname url@samestyle\endcsname
\providecommand{\newblock}{\relax}
\providecommand{\bibinfo}[2]{#2}
\providecommand{\BIBentrySTDinterwordspacing}{\spaceskip=0pt\relax}
\providecommand{\BIBentryALTinterwordstretchfactor}{4}
\providecommand{\BIBentryALTinterwordspacing}{\spaceskip=\fontdimen2\font plus
\BIBentryALTinterwordstretchfactor\fontdimen3\font minus
  \fontdimen4\font\relax}
\providecommand{\BIBforeignlanguage}[2]{{%
\expandafter\ifx\csname l@#1\endcsname\relax
\typeout{** WARNING: IEEEtranS.bst: No hyphenation pattern has been}%
\typeout{** loaded for the language `#1'. Using the pattern for}%
\typeout{** the default language instead.}%
\else
\language=\csname l@#1\endcsname
\fi
#2}}
\providecommand{\BIBdecl}{\relax}
\BIBdecl

\bibitem{JSCC:Abbasfar200704}
A.~Abbasfar, D.~Divsalar, and K.~Yao, ``Accumulate-repeat-accumulate codes,''
  \emph{{IEEE} Trans. Commun.}, vol.~55, no.~4, pp. 692--702, Apr. 2007.

\bibitem{JSCC:Andrews198311}
G.~E. Andrews, ``{Euler}'s pentagonal number theorem,'' \emph{Mathematics
  Magazine}, vol.~56, no.~5, pp. 279--284, Nov. 1983.

\bibitem{JSCC:Bennatan200403}
A.~Bennatan and D.~Burshtein, ``On the application of {LDPC} codes to arbitrary
  discrete-memoryless channels,'' \emph{{IEEE} Trans. Inf. Theory}, vol.~50,
  no.~3, pp. 417--437, Mar. 2004.

\bibitem{JSCC:Berrou199305}
C.~Berrou, A.~Glavieux, and P.~Thitimajshima, ``Near {Shannon} limit
  error-correcting coding and decoding: {Turbo} codes,'' in \emph{Proc. Int.
  Conf. Commun.}, Geneva, Switzerland, May 1993, pp. 1064--1070.

\bibitem{JSCC:Coleman200608}
T.~P. Coleman, A.~H. Lee, M.~M\'{e}dard, and M.~Effros, ``Low-complexity
  approaches to {Slepian-Wolf} near-lossless distributed data compression,''
  \emph{{IEEE} Trans. Inf. Theory}, vol.~52, no.~8, pp. 3546--3561, Aug. 2006.

\bibitem{JSCC:Como2008}
G.~Como and F.~Fagnani, ``Average spectra and minimum distances of low-density
  parity-check codes over abelian groups,'' \emph{SIAM J. Discret. Math.},
  vol.~23, no.~1, pp. 19--53, 2008.

\bibitem{JSCC:Cooper200010}
C.~Cooper, ``On the distribution of rank of a random matrix over a finite
  field,'' \emph{Random Struct. Algorithms}, vol.~17, no. 3-4, pp. 197--212,
  2000.

\bibitem{JSCC:Csiszar198100}
I.~Csisz\'{a}r and J.~K{\"{o}}rner, \emph{Information Theory: Coding Theorems
  for Discrete Memoryless Systems}.\hskip 1em plus 0.5em minus 0.4em\relax New
  York: Academic Press, 1981.

\bibitem{JSCC:Delsarte197800}
P.~Delsarte, ``Bilinear forms over a finite field, with applications to coding
  theory,'' \emph{Journal of Combinatorial Theory, Series A}, vol.~25, pp.
  226--241, 1978.

\bibitem{JSCC:Divsalar199809}
D.~Divsalar, H.~Jin, and R.~J. McEliece, ``Coding theorems for ``{Turbo}-like''
  codes,'' in \emph{Proc. 36th Allerton Conf. on Commun., Control, and
  Comput.}, Allerton, IL, Sep. 1998, pp. 201--210.

\bibitem{JSCC:Gabidulin198501}
E.~M. Gabidulin, ``Theory of codes with maximum rank distance,'' \emph{Problems
  of Information Transmission}, vol.~21, no.~1, pp. 1--12, 1985.

\bibitem{JSCC:Gallager196300}
R.~G. Gallager, \emph{Low-Density Parity-Check Codes}.\hskip 1em plus 0.5em
  minus 0.4em\relax Cambridge, MA: MIT Press, 1963.

\bibitem{JSCC:Gallager196800}
------, \emph{Information Theory and Reliable Communications}.\hskip 1em plus
  0.5em minus 0.4em\relax New York: Wiley, 1968.

\bibitem{JSCC:Garcia200103}
J.~Garcia-Frias, ``Joint source-channel decoding of correlated sources over
  noisy channels,'' in \emph{Proc. Data Compression Conf.}, Mar. 2001, pp.
  283--292.

\bibitem{JSCC:Garcia200709}
J.~Garcia-Frias, Y.~Zhao, and W.~Zhong, ``{Turbo}-like codes for transmission
  of correlated sources over noisy channels,'' \emph{{IEEE} Signal Process.
  Mag.}, vol.~24, no.~5, pp. 58--66, Sep. 2007.

\bibitem{JSCC:Honold200100}
T.~Honold and I.~Landjev, ``Mac{W}illiams identities for linear codes over
  finite {F}robenius rings,'' in \emph{Finite Fields and Applications},
  D.~Jungnickel and H.~Niederreiter, Eds.\hskip 1em plus 0.5em minus
  0.4em\relax Springer-Verlag, 2001, pp. 276--292,
  \href{http://www.ams.org/mathscinet-getitem?mr=1849094}{MR1849094}.

\bibitem{JSCC:Honold200106}
\BIBentryALTinterwordspacing
T.~Honold, ``Characterization of finite {F}robenius rings,'' \emph{Archiv der
  Mathematik}, vol.~76, no.~6, pp. 406--415, 2001,
  \href{http://www.ams.org/mathscinet-getitem?mr=1831096}{MR1831096}. [Online].
  Available: \url{http://www.springerlink.com/content/qlwp22n6hyhgx45d}
\BIBentrySTDinterwordspacing

\bibitem{JSCC:Hsu200600}
C.-H. Hsu, ``Design and analysis of capacity-achieving codes and optimal
  receivers with low complexity,'' Ph.D. dissertation, University of Michigan,
  2006.

\bibitem{JSCC:Huffman200300}
W.~C. Huffman and V.~Pless, \emph{Fundamentals of Error-Correcting
  Codes}.\hskip 1em plus 0.5em minus 0.4em\relax New York: Cambridge University
  Press, 2003.

\bibitem{JSCC:Jaspar200706}
X.~Jaspar, C.~Guillemot, and L.~Vandendorpe, ``Joint source-channel {Turbo}
  techniques for discrete-valued sources: From theory to practice,''
  \emph{Proc. {IEEE}}, vol.~95, no.~6, pp. 1345--1361, Jun. 2007.

\bibitem{JSCC:Lam1999}
T.~Y. Lam, \emph{Lectures on Modules and Rings}, ser. Graduate Texts in
  Mathematics.\hskip 1em plus 0.5em minus 0.4em\relax Springer-Verlag, 1999,
  no. 189.

\bibitem{JSCC:MacKay199903}
D.~J.~C. MacKay, ``Good error-correcting codes based on very sparse matrices,''
  \emph{{IEEE} Trans. Inf. Theory}, vol.~45, no.~2, pp. 399--431, Mar. 1999.

\bibitem{JSCC:MacWilliams196300}
F.~J. MacWilliams, ``A theorem on the distribution of weights in a systematic
  code,'' \emph{Bell System Tech. Journal}, vol.~42, pp. 79--94, 1963.

\bibitem{JSCC:Muramatsu200510}
J.~Muramatsu, T.~Uyematsu, and T.~Wadayama, ``Low-density parity-check matrices
  for coding of correlated sources,'' \emph{{IEEE} Trans. Inf. Theory},
  vol.~51, no.~10, pp. 3645--3654, Oct. 2005.

\bibitem{JSCC:Murugan200408}
A.~D. Murugan, P.~K. Gopala, and H.~E. Gamal, ``Correlated sources over
  wireless channels: Cooperative source-channel coding,'' \emph{{IEEE} J. Sel.
  Areas Commun.}, vol.~22, no.~6, pp. 988--998, Aug. 2004.

\bibitem{JSCC:Nechaev200800}
A.~A. Nechaev, ``Finite rings with applications,'' in \emph{Handbook of
  Algebra}, M.~Hazewinkel, Ed.\hskip 1em plus 0.5em minus 0.4em\relax Elsevier
  Science Publishers, 2008, vol.~5, ch.~5, pp. 213--320.

\bibitem{JSCC:Pfister200306}
H.~D. Pfister and P.~H. Siegel, ``The serial concatenation of rate-1 codes
  through uniform random interleavers,'' \emph{{IEEE} Trans. Inf. Theory},
  vol.~49, no.~6, pp. 1425--1438, Jun. 2003.

\bibitem{JSCC:Pless199800}
V.~S. Pless, W.~C. Huffman, and R.~A. Brualdi, ``An introduction to algebraic
  codes,'' in \emph{Handbook of Coding Theory}, V.~S. Pless and W.~C. Huffman,
  Eds.\hskip 1em plus 0.5em minus 0.4em\relax Amsterdam: Elsevier Science
  Publishers, 1998, vol.~I, ch.~1, pp. 3--139.

\bibitem{JSCC:Pradhan200100}
S.~S. Pradhan, ``Distributed source coding using syndromes {(DISCUS)},'' Ph.D.
  dissertation, University of California at Berkeley, fall 2001.

\bibitem{JSCC:Roth199103}
R.~M. Roth, ``Maximum-rand array codes and their application to crisscross
  error correction,'' \emph{{IEEE} Trans. Inf. Theory}, vol.~37, no.~2, pp.
  328--336, Mar. 1991.

\bibitem{JSCC:Shulman199909}
N.~Shulman and M.~Feder, ``Random coding techniques for nonrandom codes,''
  \emph{{IEEE} Trans. Inf. Theory}, vol.~45, no.~6, pp. 2101--2104, Sep. 1999.

\bibitem{JSCC:Silva200809}
D.~Silva, F.~Kschischang, and R.~Koetter, ``A rank-metric approach to error
  control in random network coding,'' \emph{{IEEE} Trans. Inf. Theory},
  vol.~54, no.~9, pp. 3951--3967, Sep. 2008.

\bibitem{JSCC:Simonis199502}
J.~Simonis, ``{MacWilliams} identities and coordinate partitions,''
  \emph{Linear Algebra and its Applications}, vol. 216, pp. 81--91, Feb. 1995.

\bibitem{JSCC:Stankovic200604}
V.~Stankovi\'{c}, A.~D. Liveris, Z.~Xiong, and C.~N. Georghiades, ``On code
  design for the {Slepian-Wolf} problem and lossless multiterminal networks,''
  \emph{{IEEE} Trans. Inf. Theory}, vol.~52, no.~4, pp. 1495--1507, Apr. 2006.

\bibitem{JSCC:Wood199903}
J.~A. Wood, ``Duality for modules over finite rings and applications to coding
  theory,'' \emph{American Journal of Mathematics}, vol. 121, no.~3, pp.
  555--575, 1999.

\bibitem{JSCC:Yang201008}
S.~Yang, ``A note on good random matrices over finite fields,'' \emph{{IEEE}
  Commun. Lett.}, 2010, submitted for publication, draft available at
  http://arxiv.org/abs/1008.3408.

\bibitem{JSCC:Yang200904}
S.~Yang, Y.~Chen, and P.~Qiu, ``Linear-codes-based lossless joint
  source-channel coding for multiple-access channels,'' \emph{{IEEE} Trans.
  Inf. Theory}, vol.~55, no.~4, pp. 1468--1486, Apr. 2009.

\bibitem{JSCC:Yang201004}
S.~Yang, T.~Honold, Y.~Chen, Z.~Zhang, and P.~Qiu, ``Weight distributions of
  regular low-density parity-check codes over finite fields,'' in preparation,
  to be submitted to \emph{IEEE Trans. Inf. Theory}.

\bibitem{JSCC:Yang200503}
S.~Yang and P.~Qiu, ``On the performance of linear {Slepian-Wolf} codes for
  correlated stationary memoryless sources,'' in \emph{Proc. Data Compression
  Conf.}, Snowbird, UT, Mar. 2005, pp. 53--62.

\bibitem{JSCC:Zhao200611a}
Y.~Zhao and J.~Garcia-Frias, ``{Turbo} compression/joint source-channel coding
  of correlated binary sources with hidden {Markov} correlation,'' \emph{Signal
  Processing}, vol.~86, no.~11, pp. 3115--3122, 2006.

\bibitem{JSCC:Zhao200611b}
Y.~Zhao, W.~Zhong, and J.~Garcia-Frias, ``Transmission of correlated senders
  over a {Rayleigh} fading multiple access channel,'' \emph{Signal Processing},
  vol.~86, no.~11, pp. 3150--3159, 2006.

\bibitem{JSCC:Zhong200505}
W.~Zhong and J.~Garcia-Frias, ``{LDGM} codes for channel coding and joint
  source-channel coding of correlated sources,'' \emph{EURASIP Journal on
  Applied Signal Processing}, vol. 2005, no.~6, pp. 942--953, 2005.

\bibitem{JSCC:Zhu200408}
G.-C. Zhu, F.~Alajaji, J.~Bajcsy, and P.~Mitran, ``Transmission of nonuniform
  memoryless sources via nonsystematic {Turbo} codes,'' \emph{{IEEE} Trans.
  Commun.}, vol.~52, no.~8, pp. 1344--1354, Aug. 2004.

\end{thebibliography}
