大家好，我是讯享网，很高兴认识大家。

本文 largely based on Prof. Kschischang 和 Chen Feng 2014 年给的 tutorial。原 tutorial 的标题是 “An Introduction to Lattices and their Applications in Communications”. Slides 在网上可以下载到。

Lattice 基础

---

Notations

我们将使用的一些符号：
$\mathbb{R},\mathbb{C}$: 实数域和复数域。所谓域 (field) 是指一种可进行加减乘除(当然不能除以零之外，“零” 即加法单位元）运算的代数结构。如果域中元素个数有限，那就是有限域finite field.

$\mathbb{Z}$: 整数环 (ring)。所有的整数不构成域，因为整数的倒数一般不是整数。环 (ring) 是由集合R和定义于其上的两种二元运算（常被简称为加和乘，但与一般所说的加法和乘法不同）所构成的。

X n = { ( x 1 , x 2 , . . . , x n ) : x 1 , . . . x n ∈ X } X^n=\left\{(x_1,x_2,...,x_n):x_1,...x_n\in X\right\} Xn={ (x1​,x2​,...,xn​):x1​,...xn​∈X}: 一个set $X$ 自身的 $n$ 重笛卡儿积 ($n$-fold Cartesian product). 如果set $X$ 本身是一个域，那么 $X^n$ 的每一个元素都是一个行向量。简而言之就是把set $X$ 扩充到 $n$ 维。

$X^{m\times n}$: size 为 $m\times n$ 的矩阵，且每个元素都是从 $X$ 中选取的。所以上方 $n$ 重笛卡儿积的定义也可以写为 $X^{1\times n}$。本文中一般使用行向量 instead of 列向量。

$(G,+)$: 表示一个群， G ∗ = G   \ { 0 } G^*=G~\backslash\{0\} G∗=G \{ 0} 表示群 $G$ 除了加法单位元 $0$ 之外的所有元素的集合。Note: 群（group）是由一种集合以及一个二元运算所组成的，并且符合“群公理”: 封闭性、结合律、单位元和对于集合中所有元素存在逆元素。

---

Euclidean Space

我们把一个有限维的 Euclidean space 记作 ${\mathbb{R}}^n$. 对于${\mathbb{R}}^n$ 中的任意两个元素 $\mathbf{x}$ 和 $\mathbf{y}$，我们定义

1. 内积 inner product: $<\mathbf{x},\mathbf{y}>={\sum }_{i=1}^n{x}_i{y}_i$. 对应坐标元素相乘再相加, 内积为0时两个向量垂直;
2. 范数 norm: $\Vert \mathbf{x}\Vert =\sqrt{<\mathbf{x},\mathbf{x}>}$;
3. metric: $d(\mathbf{x},\mathbf{y})=\Vert \mathbf{x}-\mathbf{y}\Vert$.
4. 令 $\mathcal{R}$ 为 ${\mathbb{R}}^n$ 的一个subset，那么 $\mathcal{R}$ 关于 $\mathbf{x}$ 的 translation 是把 $\mathcal{R}$ 平移 $\mathbf{x}$ 后得到的set, 即 x + R = { x + y , y ∈ R } \bm{x}+\mathcal{R}=\{\bm{x+y},\bm{y}\in\mathcal{R}\} x+R={ x+y,y∈R}.
5. Ball B r = { x ∈ R n : ∥ x ∥ ≤ r } \mathcal{B}_r=\left\{\bm{x}\in\mathbb{R}^n:\|\bm{x}\|\leq r\right\} Br​={ x∈Rn:∥x∥≤r}，这是一个圆心在 origin 半径为 $r$ 的 $n$ 维球。

其中，$n$ 维球的体积为
$$V({\mathcal{B}}_r)=\frac{{\pi }^{n/2}}{\Gamma (\frac{n}{2}+1)}{r}^n$$

分母中 $\Gamma$ 把阶乘拓展到了非整数域，我们也可以把 $\Gamma (\frac{n}{2}+1)$ 记作 $\frac{n}{2}!$. By Stirling’s approximation, 我们进一步可以得到一个 asymptotic formula:
$$V({\mathcal{B}}_r)\approx \frac{1}{\sqrt{n\pi }}{\left(\frac{2\pi e}{n}\right)}^{n/2}{r}^n$$.

---

Lattice Definition

我们现在可以定义 lattice 了. 在一下定义中，我们只关心 $m=n$ 的情况，即 lattice 铺满整个空间 ${\mathbb{R}}^n$, 而非仅存在于其subspace ${\mathbb{R}}^m$.

讯享网
其中

1. $\text{dim}(\Lambda )=n$;
2. $\text{rank}(\Lambda )=n$;
3. ${\mathbf{g}}_1,{\mathbf{g}}_2,...,{\mathbf{g}}_{\mathbf{n}}$ 这组线性无关的向量被称为 generators of $\Lambda$

简而言之，lattice就是$R^n$ 用 generators 的整数倍线性组合能得到的所有离散点。按照群的定义，也可以说 Lattice is a subgroup of ${\mathbb{R}}^n$.

举两个例子:

---

Lattice Generator Matrix

先然，我们可以把 $\Lambda$ 写成矩阵形式。首先，$n$ 个 线性无关的 generators ${\mathbf{g}}_{\mathbf{i}}$ 可以组成一个满秩矩阵，记作
$${\mathbf{G}}_{\Lambda }=\left[\begin{array}{c}{\mathbf{g}}_1\\ {\mathbf{g}}_2\\ ...\\ {\mathbf{g}}_{\mathbf{n}}\end{array}\right]$$

那么，Lattice
Λ = { c G Λ : c ∈ Z n } \Lambda=\{c\bm{G}_\Lambda: c\in\mathbb{Z}^n\} Λ={ cGΛ​:c∈Zn}

在上面的两个例子中，实际上最后生成的 lattice 是一模一样的. 但是由于我们使用了不同的generators，因此也有不同的生成矩阵。这意味着 同一个lattice有不同的生成矩阵，那么，一个自然的问题是，什么样的生成矩阵能生成同样的 lattice 尼？

这个定理很好理解，生成矩阵可以是小数，但是他们可以通过一个 unimodular matrix $\mathbf{U}$ 相互转换。注意，unimodular matrix是一个整数矩阵且行列式 det ( U ) = { 1 , − 1 } \text{det}(\bm{U})=\{1,-1\} det(U)={ 1,−1}. 等价的，我们可以定义它为整数域上可逆的整数矩阵，即它的逆仍然是 unimodular matrix. 而且显然两个unimodular matrix 的乘积仍然是unimodular matrix (仍是整数，且行列式仍是1 or -1).

---

Lattice Determinant

Lattice 的生成矩阵之间可以用 unimodular matrix相互转换，因此他们的determinant之间只差一个系数 1 或 -1. 换句话说，lattice的determinant是不随生成矩阵而变化的

这种不变性有很重要的几何意义，因为我们都知道矩阵的行列式实际上就是它的各行(或者各列) 生成的平行六面体 (parallelepiped) 的体积。这就意味着对于任何生成矩阵来说，他们的各行生成的 parallelepiped 体积都是相同的。下面我们给出严格的定义。

它的 volume
$$V(\mathcal{P}({\mathbf{g}}_1,...,{\mathbf{g}}_{\mathbf{n}}))=\text{det}(\Lambda )=|\text{det}({\mathbf{G}}_{\Lambda })|$$

两个简单的例子如下所示。

---

Lattice Fundamental Region

接下来我们讲一下 fundamental region。实际上fundamental parallelepiped 也是一种 fundamental region，只要carefully选择边界即可。

显然，所谓的 fundamental region 就是围绕在每个 lattice point 周围的一部分region。他们在一起覆盖了整个空间 ${\mathbb{R}}^n$ 但又相互不重叠。下面我们给出同一lattice的一些fundamental region

可以看到，fundamental region 不唯一，而且甚至不用是 connected set。但是需要注意的一点是，fundamental region不存在两个差为nonzero lattice point 的点。换句话说，对于任意一个fundamental region里的点，平移某个generator之后必然得跳出fundamental region了，不然会overlap。

每个fundamental region都有同样的volume，$\text{det}(\Lambda )$。

下面介绍另一种特殊的fundamental region – the Voronoi region.

对于某个lattice 点 $\lambda$, 这个特殊的 Voronoi region $\mathcal{V}(\lambda )$ 的要求是， $\mathcal{V}(\lambda )$ 种所有点到 $\lambda$ 比到其他 lattice points 都要近。这也就意味着这个region是规则的lattice之间的等分region，如下图所示

其实也可以看到 Voronoi region 是很重要的，因为我们单独给了它一个符号 $\mathcal{V}$. 特别的，Lattice point $\mathbf{\lambda }=0$ 的 region 被称为 the Voronoi region of the lattice, 记作 $\mathcal{V}(\Lambda )$.

---

Minimum Distance and Successive Minima

lattice 本身具有一些距离属性，定义如下。

首先，minimum distance 是非零 lattice points 距离零最近的距离
$$d_{\text{min}}(\Lambda )=\underset{\lambda \in {\Lambda }^{\ast }}{\min }\Vert \lambda \Vert$$

紧接着我们定义 lattice 的successive minima $L_i(\Lambda )$，即包含 $i$ 个线性无关的lattice vectors 的最小ball的半径。

显然，$L_1(\Lambda )=d_{\text{min}}(\Lambda )$. 另外需要注意的是，虽然 $L_n(\Lambda )$ 中有 $n$ 个线性无关的 vector，但这不代表这$n$ 个线性无关的 vector可以张成exactly the same lattice。

---

Quick Summary

Lattice的几个regions:

给定一个 lattice,

1. 它有不唯一的生成矩阵，不同生成矩阵行列式的abs都是一样的，记为 $\text{det}(\Lambda )$.
2. 每个生成矩阵对应一个fundamental parallelepiped，体积都是$\text{det}(\Lambda )$.
3. 它有无穷个fundamental region，体积也都是$\text{det}(\Lambda )$.
4. 一种特殊的fundamental region是Voronoi region，等分所有lattice points.
5. The Voronoi region of the lattice 就是 lattice point 0 的 Voronoi region.

关于 Lattice 本身的一些属性：

1. generators and generator matrix ${\mathbf{G}}_{\Lambda }$ (不唯一);
2. determinant $\text{det}(\Lambda )=|\text{det}({\mathbf{G}}_{\Lambda })|$ (fixed);
3. Voronoi region $\mathcal{V}(\Lambda )=\mathcal{V}(0)$;
4. minimum distance $d_{\text{min}}(\Lambda )$ and successive minima $L_i(\Lambda )$;

---

下面我们研究 lattice 和 lattice 之间的关系

Dual Lattice

可以看到，${\Lambda }^{\perp }$ 中的向量 $\mathbf{x}$，跟 $\Lambda$ 中的任意 lattice point $\lambda$ 的内积都是整数.

以上 fact 也告诉我们

1. $\text{det}(\Lambda )\ast \text{det}({\Lambda }^{\perp })=1$;
2. ${\Lambda }^{\perp }$ 的生成矩阵可以作为 $\Lambda$ 生成矩阵的 parity-check matrix.

---

Nested Lattices

现在我们研究lattice的嵌套。这是 lattice 比较重要的性质因此我们要稍微多说一点。

如下图所示，${\Lambda }^{\prime }$ 嵌套入 $\Lambda$，此时我们分别称 $\Lambda$ as the fine lattice while ${\Lambda }^{\prime }$ as the coarse lattice. 记作
$${\Lambda }^{\prime }\subseteq \Lambda$$

而且，如果${\Lambda }^{\prime }$ 能嵌套入 $\Lambda$，那说明 ${\Lambda }^{\prime }$ 的元素也是属于$\Lambda$的，可以用 $\Lambda$的 generator matrix 来产生。特别的，他们的generator matrix 必须满足以下关系
$${\mathbf{G}}_{{\Lambda }^{\prime }}={\mathbf{J}\mathbf{G}}_{\Lambda }$$

其中整数矩阵 $\mathbf{J}$ 被称为 nesting matrix. $\mathbf{J}$ 有以下性质：

1. 不管怎么选 ${\mathbf{G}}_{{\Lambda }^{\prime }},{\mathbf{G}}_{\Lambda }$,
   $$\text{det}(\mathbf{J})=\frac{\text{det}({\mathbf{\Lambda }}^{\prime })}{\text{det}(\mathbf{\Lambda })}$$
   由于RHS只会变换符号，因此 $|\text{det}(\mathbf{J})|$ 是fix不变的。
2. 一旦 ${\mathbf{G}}_{{\Lambda }^{\prime }},{\mathbf{G}}_{\Lambda }$ 给定 $\mathbf{J}$ 也唯一确定；而且总能找到一组 ${\mathbf{G}}_{{\Lambda }^{\prime }},{\mathbf{G}}_{\Lambda }$ 使得 $\mathbf{J}$ 是一个对角阵。 这在如下theorem 中阐述。

[Q] here, the vertical bar between $c_i$ means divisibility? does not make sense!

其中，$c_1,c_2,...,c_n$ 被称为nesting matrix 的 invariance factors. 为了证明确实存在这样的diagonal nesting matrix, 我们先来看看矩阵的 Smith Normal Form.

从这个定义上看，principal ideal domain (PID) 中的任意非零矩阵 $\mathbf{A}$ 都能被对角化。而这种对角化被称为 the Smith Normal Form of $\mathbf{A}$：
$$\mathbf{A}={\mathbf{P}}^{-1}\mathbf{D}{\mathbf{Q}}^{-1}$$

好，现在让我们回到 nesting matrix
$${\mathbf{G}}_{{\Lambda }^{\prime }}={\mathbf{J}\mathbf{G}}_{\Lambda }$$

上面的叙述主要是想说存在2个 unimodular matrices $\mathbf{U},\mathbf{V}$ 可以使 $\mathbf{J}$ 对角化，即
$$\mathbf{J}={\mathbf{U}}^{-1}\mathbf{D}{\mathbf{V}}^{-1}$$

则
$${\mathbf{G}}_{{\Lambda }^{\prime }}={\mathbf{U}}^{-1}\mathbf{D}{\mathbf{V}}^{-1}{\mathbf{G}}_{\Lambda }$$

$$(\mathbf{U}{\mathbf{G}}_{{\Lambda }^{\prime }})=\mathbf{D}({\mathbf{V}}^{-1}{\mathbf{G}}_{\Lambda })$$

$${\mathbf{G}}_{{\Lambda }^{\prime }}^{\prime }=\mathbf{D}{\mathbf{G}}_{\Lambda }^{\prime }$$

即，用 $\mathbf{U},\mathbf{V}$ 分别对原来的 ${\mathbf{G}}_{{\Lambda }^{\prime }},{\mathbf{G}}_{\Lambda }$ 进行变换即可得到两个 lattice 新的 generator matrices 从而使得 nesting matrix 是diagonal的。

---

Labeling the Nested Lattice

给定一对 nested lattice $(\Lambda ,{\Lambda }^{\prime })$, 我们可以对 ${\Lambda }^{\prime }$ 的 fundamental parallelepiped 中 $\Lambda$ 的元素进行label.

比如说，给定一对 nested lattices
$${\mathbf{G}}_{{\Lambda }^{\prime }}=\text{diag}(c_1,c_2,...,c_n){\mathbf{G}}_{\Lambda }$$

${\Lambda }^{\prime }$ 的 fundamental parallelepiped 中，每个lattice points 可以记作
$$(a_1,a_2,...,a_n){\mathbf{G}}_{\Lambda }$$

其中 $0\le a_i\le c_i$, $i=1,2,...,n$.

下图是一个 ${\mathbf{G}}_{{\Lambda }^{\prime }}=\text{diag}(2,4){\mathbf{G}}_{\Lambda }$ 的例子, 在${\Lambda }^{\prime }$ 的 fundamental parallelepiped 中, 总共有 $\text{det}(\mathbf{J})={\prod }_{i=1}^n{c}_i$ 个点, 我们可以按照上式对所有的点进行label.

这种label方式可以进一步periodically extend 到整个lattice $\Lambda$

如上图所示，此时 label 也是 linear 的，即两个 lattice points 和的label等于它们label的和 (在各个维度模 $c_n$), 即
$$\ell ({\lambda }_1+{\lambda }_2)=\ell ({\lambda }_1)+\ell ({\lambda }_2)$$

Complex Lattice

在本节的最后，我们讲一下complex lattice。在通信中我们的 baseband 信号是 complex 的 (after QAM modulation).

注意这里的定义和实数情况下并无二致. 我们让 $m=n$, 那么这个 $n$ 维空间中所有点都是一个complex number，因此这些系数 $c_i$ 也应该是complex integer (具体不再展开讲)。注意一般在通信中，我们讲 constellation，那是把复数当做二维实数来看 (复平面)，这里每一个维度都可以看做一个复平面。