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

Lattice 基础

---

Notations

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

Z \mathbb{Z} 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 X X 自身的 n n n 重笛卡儿积 ( n n n-fold Cartesian product). 如果set X X X 本身是一个域，那么 X n X^n Xn 的每一个元素都是一个行向量。简而言之就是把set X X X 扩充到 n n n 维。

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

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

---

Euclidean Space

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

1. 内积 inner product: < x , y > = ∑ i = 1 n x i y i <\bm{x},\bm{y}>=\sum_{i=1}^n x_iy_i <x,y>=∑i=1n​xi​yi​. 对应坐标元素相乘再相加, 内积为0时两个向量垂直;
2. 范数 norm: ∥ x ∥ = < x , x > \|\bm{x}\|=\sqrt{<\bm{x},\bm{x}>} ∥x∥=<x,x> ​;
3. metric: d ( x , y ) = ∥ x − y ∥ d(\bm{x,y})=\|\bm{x-y}\| d(x,y)=∥x−y∥.
4. 令 R \mathcal{R} R 为 R n \mathbb{R}^n Rn 的一个subset，那么 R \mathcal{R} R 关于 x \bm{x} x 的 translation 是把 R \mathcal{R} R 平移 x \bm{x} 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 r r 的 n n n 维球。

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

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

---

Lattice Definition

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

其中

1. dim ( Λ ) = n \text{dim}(\Lambda)=n dim(Λ)=n;
2. rank ( Λ ) = n \text{rank}(\Lambda)=n rank(Λ)=n;
3. g 1 , g 2 , . . . , g n \bm{g_1},\bm{g_2},...,\bm{g_n} g1​,g2​,...,gn​ 这组线性无关的向量被称为 generators of Λ \Lambda Λ

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

举两个例子:

---

Lattice Generator Matrix

先然，我们可以把 Λ \Lambda Λ 写成矩阵形式。首先， n n n 个 线性无关的 generators g i \bm{g_i} gi​ 可以组成一个满秩矩阵，记作
G Λ = [ g 1 g 2 . . . g n ] \bm{G}_\Lambda=\begin{bmatrix} \bm{g_1} \\ \bm{g_2} \\ ... \\ \bm{g_n} \end{bmatrix} GΛ​=⎣⎢⎢⎡​g1​g2​...gn​​⎦⎥⎥⎤​

那么，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 U \bm{U} 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 ( P ( g 1 , . . . , g n ) ) = det ( Λ ) = ∣ det ( G Λ ) ∣ V(\mathcal{P}(\bm{g_1,...,g_n}))=\text{det}(\Lambda)=|\text{det}(\bm{G}_\Lambda)| V(P(g1​,...,gn​))=det(Λ)=∣det(GΛ​)∣

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

---

Lattice Fundamental Region

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

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

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

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

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

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

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

---

Minimum Distance and Successive Minima

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

首先，minimum distance 是非零 lattice points 距离零最近的距离
d min ( Λ ) = min ⁡ λ ∈ Λ ∗ ∥ λ ∥ d_\text{min}(\Lambda)=\min_{\lambda\in\Lambda^*} \|\lambda\| dmin​(Λ)=λ∈Λ∗min​∥λ∥

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

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

---

Quick Summary

Lattice的几个regions:

给定一个 lattice,

1. 它有不唯一的生成矩阵，不同生成矩阵行列式的abs都是一样的，记为 det ( Λ ) \text{det}(\Lambda) det(Λ).
2. 每个生成矩阵对应一个fundamental parallelepiped，体积都是 det ( Λ ) \text{det}(\Lambda) det(Λ).
3. 它有无穷个fundamental region，体积也都是 det ( Λ ) \text{det}(\Lambda) det(Λ).
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 G Λ \bm{G}_{\Lambda} GΛ​ (不唯一);
2. determinant det ( Λ ) = ∣ det ( G Λ ) ∣ \text{det}(\Lambda)=|\text{det}(\bm{G}_{\Lambda})| det(Λ)=∣det(GΛ​)∣ (fixed);
3. Voronoi region V ( Λ ) = V ( 0 ) \mathcal{V}(\Lambda)=\mathcal{V}(0) V(Λ)=V(0);
4. minimum distance d min ( Λ ) d_\text{min}(\Lambda) dmin​(Λ) and successive minima L i ( Λ ) L_i(\Lambda) Li​(Λ);

---

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

Dual Lattice

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

以上 fact 也告诉我们

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

---

Nested Lattices

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

如下图所示， Λ ′ \Lambda' Λ′ 嵌套入 Λ \Lambda Λ，此时我们分别称 Λ \Lambda Λ as the fine lattice while Λ ′ \Lambda' Λ′ as the coarse lattice. 记作
Λ ′ ⊆ Λ \Lambda'\subseteq\Lambda Λ′⊆Λ

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

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

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

[Q] here, the vertical bar between c i c_i ci​ means divisibility? does not make sense!

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

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

好，现在让我们回到 nesting matrix
G Λ ′ = J G Λ \bm{G}_{\Lambda'}=\bm{JG}_{\Lambda} GΛ′​=JGΛ​

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

则
G Λ ′ = U − 1 D V − 1 G Λ \bm{G}_{\Lambda'}=\bm{U}^{-1}\bm{D}\bm{V}^{-1}\bm{G}_{\Lambda} GΛ′​=U−1DV−1GΛ​

( U G Λ ′ ) = D ( V − 1 G Λ ) (\bm{U}\bm{G}_{\Lambda'})=\bm{D}(\bm{V}^{-1}\bm{G}_{\Lambda}) (UGΛ′​)=D(V−1GΛ​)

G Λ ′ ′ = D G Λ ′ \bm{G}^\prime_{\Lambda'}=\bm{D}\bm{G}^\prime_{\Lambda} GΛ′′​=DGΛ′​

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

---

Labeling the Nested Lattice

给定一对 nested lattice ( Λ , Λ ′ ) (\Lambda,\Lambda') (Λ,Λ′), 我们可以对 Λ ′ \Lambda' Λ′ 的 fundamental parallelepiped 中 Λ \Lambda Λ 的元素进行label.

比如说，给定一对 nested lattices
G Λ ′ = diag ( c 1 , c 2 , . . . , c n ) G Λ \bm{G}_{\Lambda'}=\text{diag}(c_1,c_2,...,c_n)\bm{G}_{\Lambda} GΛ′​=diag(c1​,c2​,...,cn​)GΛ​

Λ ′ \Lambda' Λ′ 的 fundamental parallelepiped 中，每个lattice points 可以记作
( a 1 , a 2 , . . . , a n ) G Λ (a_1,a_2,...,a_n)\bm{G}_{\Lambda} (a1​,a2​,...,an​)GΛ​

其中 0 ≤ a i ≤ c i 0\leq a_i \leq c_i 0≤ai​≤ci​, i = 1 , 2 , . . . , n i=1,2,...,n i=1,2,...,n.

下图是一个 G Λ ′ = diag ( 2 , 4 ) G Λ \bm{G}_{\Lambda'}=\text{diag}(2,4)\bm{G}_{\Lambda} GΛ′​=diag(2,4)GΛ​ 的例子, 在 Λ ′ \Lambda' Λ′ 的 fundamental parallelepiped 中, 总共有 det ( J ) = ∏ i = 1 n c i \text{det}(\bm{J})=\prod_{i=1}^n c_i det(J)=∏i=1n​ci​ 个点, 我们可以按照上式对所有的点进行label.

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

如上图所示，此时 label 也是 linear 的，即两个 lattice points 和的label等于它们label的和 (在各个维度模 c n c_n cn​), 即
ℓ ( λ 1 + λ 2 ) = ℓ ( λ 1 ) + ℓ ( λ 2 ) \ell(\lambda_1+\lambda_2)=\ell(\lambda_1)+\ell(\lambda_2) ℓ(λ1​+λ2​)=ℓ(λ1​)+ℓ(λ2​)

Complex Lattice

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

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

---

---

---

Packing, Covering, Quantization, Modulation

再讲了大一堆概念之后，我们终于可以开始来看看 lattice 的一些性质了。其实lattice有很好的几何含义，因此实际上关于 lattice的概念和性质都还是很好理解的。

首先一个问题就是 packing。还记得第一讲中的 n n n 维球 B r \mathcal{B}_r Br​ 么，我们首先研究怎么用lattice来pack balls。为了方便叙述，我们进一步定义

1. Unit-radius ball 的 Volume:
   Vol ( B 1 ) = V n \text{Vol}(\mathcal{B}_1)=V_n Vol(B1​)=Vn​
2. B r = r B 1 = { r x : x ∈ B 1 } \mathcal{B}_r=r\mathcal{B}_1=\{r\bm{x}:\bm{x}\in\mathcal{B}_1\} Br​=rB1​={rx:x∈B1​} 的Volume
   Vol ( B r ) = r n Vol ( B 1 ) = r n V n \text{Vol}(\mathcal{B}_r)=r^n\text{Vol}(\mathcal{B}_1)=r^nV_n Vol(Br​)=rnVol(B1​)=rnVn​

---

Sphere Packing

好，现在我们用Lattice来填球。注意我们是要在每个lattice point上一起填球，而填充半径packing radius也就定义最大能塞进去的球的半径。

Visually, 显然我们只用考虑在 Voronoi region V ( Λ ) \mathcal{V}(\Lambda) V(Λ) 里面塞球就好了

我们知道lattice它的所有 fundamental region 的volume都是 det ( Λ ) \text{det}(\Lambda) det(Λ). 用这个Volume，我们可以定义出一个effective ball of radius
r eff ( Λ ) = ( det ( Λ ) V n ) 1 / n r_\text{eff}(\Lambda)=\left(\frac{\text{det}(\Lambda)}{V_n}\right)^{1/n} reff​(Λ)=(Vn​det(Λ)​)1/n

这也被称为 lattice 的 effective radius。显然这个肯定比 r pack ( Λ ) r_\text{pack}(\Lambda) rpack​(Λ) 大，Voronoi region本身为球时两者相等。自然的，我们可以定义他们的比值作为lattice 的 packing efficiency：
ρ pack ( Λ ) = r pack ( Λ ) r eff ( Λ ) \rho_\text{pack}(\Lambda)=\frac{r_\text{pack}(\Lambda)}{r_\text{eff}(\Lambda)} ρpack​(Λ)=reff​(Λ)rpack​(Λ)​

如上图所示，packing efficiency 是两个ball半径的比值，而且我们显然有

1. 0 < ρ pack ( Λ ) ≤ 1 0<\rho_\text{pack}(\Lambda)\leq 1 0<ρpack​(Λ)≤1;
2. ρ pack ( Λ ) \rho_\text{pack}(\Lambda) ρpack​(Λ) 不会随着 scaling 而变化: ρ pack ( α Λ ) = ρ pack ( Λ ) \rho_\text{pack}(\alpha\Lambda)=\rho_\text{pack}(\Lambda) ρpack​(αΛ)=ρpack​(Λ), α ≠ 0 \alpha\neq 0 α​=0.
3. 如果我们不看半径看volume的话，Volume的比值，即 packing density 为 ρ pack n ( Λ ) \rho^n_\text{pack}(\Lambda) ρpackn​(Λ).

不同样子的lattice有不同的 Voronoi region, 因此在各个维度上一定存在最好的lattice使得packing能力最强 (packing efficiency最大)。 比如 n = 2 n=2 n=2 时, hexagonal lattice 最好; n = 3 n=3 n=3 时, face-centered cubic lattice 最好, etc. 目前 n > 8 n>8 n>8 的好多还未知。The Minkowski-Hlawka Theorem 给出了 lower bound.

Sphere Covering

Sphere covering 的意思在lattice的各个points上放球以覆盖整个空间。

所需球的最小半径也就是covering radius。其实很容易看出，只要球把 Voronoi region V ( Λ ) \mathcal{V}(\Lambda) V(Λ) 给覆盖掉就行了。

如下图所示，显然 covering radius r cov ( Λ ) r_\text{cov}(\Lambda) rcov​(Λ) 就是 V ( Λ ) \mathcal{V}(\Lambda) V(Λ) 的 outer radius (能覆盖 V ( Λ ) \mathcal{V}(\Lambda) V(Λ)最小球的半径)。

类似的，我们定义 covering efficiency
ρ cov ( Λ ) = r cov ( Λ ) r eff ( Λ ) \rho_\text{cov}(\Lambda)=\frac{r_\text{cov}(\Lambda)}{r_\text{eff}(\Lambda)} ρcov​(Λ)=reff​(Λ)rcov​(Λ)​

则有

1. ρ cov ( Λ ) > 1 \rho_\text{cov}(\Lambda)>1 ρcov​(Λ)>1.
2. ρ cov ( α Λ ) = ρ cov ( Λ ) \rho_\text{cov}(\alpha\Lambda) = \rho_\text{cov}(\Lambda) ρcov​(αΛ)=ρcov​(Λ) invariant to scaling.

在各个维度上有最好的lattice使得covering efficiency最小。 比如 n = 2 n=2 n=2 时, hexagonal lattice 最好; n = 3 n=3 n=3 时, body-centered cubic lattice 最好, etc.

Quantization

Lattice 毕竟只占据了空间中的一些点，对于其他的点，我们可以考虑 quantize 它到 lattice 上的某一点去。这就是 lattice quantizer。

quantizer

quantization error

我们用 quantization error 来衡量 quantizer 的好坏. 对于空间中任意一点 x \bm{x} x, 我们定义 quantization error
x e = x − Q Λ ( x ) \bm{x_e}=\bm{x}-\mathcal{Q}_\Lambda(\bm{x}) xe​=x−QΛ​(x)

显然，他也是一个向量。

nearest-neighbor quantizer

一个最简单的 quantization scheme 就是quantize到最近的点，即 Nearest-Neighbor Quantizer.

注意这只是一个定义而已，实际上怎么去求解最近的 lattice point 不是一个简单的问题 (虽然 conceptually 很简单)。我们也可以定义 NN quantizer 的逆运算，即为 λ \lambda λ 的 Voronoi region,
[ Q Λ N N ] − 1 ( λ ) = V ( λ ) \left[ \mathcal{Q}_\Lambda^{NN} \right]^{-1}(\lambda)=\mathcal{V}(\lambda) [QΛNN​]−1(λ)=V(λ)

NN quantizer 的error 仍然在 Voronoi region 中：
x e = x − Q Λ ( N N ) ( x ) ∈ V ( Λ ) \bm{x_e}=\bm{x}-\mathcal{Q}_\Lambda^{(NN)}(\bm{x})\in\mathcal{V}(\Lambda) xe​=x−QΛ(NN)​(x)∈V(Λ)

假设 x e \bm{x_e} xe​ 在 Voronoi region 中均匀分布，那么我们定义 the second moment of the quantization error per dimension

The second moment per dimension –
σ 2 ( Λ ) = 1 n E [ ∥ x e ∥ 2 ] = 1 n 1 det ( Λ ) ∫ V ( Λ ) ∥ x e ∥ 2 d x e \sigma^2(\Lambda)=\frac{1}{n}\mathbb{E}\left[\|\bm{x_e}\|^2\right]=\frac{1}{n}\frac{1}{\text{det}(\Lambda)}\int_{\mathcal{V}(\Lambda)}\|\bm{x_e}\|^2 d \bm{x_e} σ2(Λ)=n1​E[∥xe​∥2]=n1​det(Λ)1​∫V(Λ)​∥xe​∥2dxe​

显然， σ 2 ( Λ ) \sigma^2(\Lambda) σ2(Λ) 越小，NN quantizer性能越好。因为我们假设 error 是均匀分布在 V ( Λ ) \mathcal{V}(\Lambda) V(Λ) 上的，因此 σ 2 ( Λ ) \sigma^2(\Lambda) σ2(Λ) 也是 lattice 的固有属性。

有一个问题是 σ 2 ( Λ ) \sigma^2(\Lambda) σ2(Λ) 会随着 scaling factor α \alpha α 的变化而变化：
σ 2 ( α Λ ) = 1 n 1 α n det ( Λ ) ∫ V ( Λ ) ∥ α x e ∥ 2 d ( α n x e ) = α 2 σ 2 ( Λ ) \sigma^2(\alpha\Lambda)=\frac{1}{n}\frac{1}{\alpha^n\text{det}(\Lambda)}\int_{\mathcal{V}(\Lambda)}\|\alpha\bm{x_e}\|^2 d (\alpha^n\bm{x_e})=\alpha^{2}\sigma^2(\Lambda) σ2(αΛ)=n1​αndet(Λ)1​∫V(Λ)​∥αxe​∥2d(αnxe​)=α2σ2(Λ)

因此我们可以进一步定义 the normalized second moment

The normalized second moment per dimension –
G ( Λ ) = σ 2 ( Λ ) det ( Λ ) 2 / n G(\Lambda)=\frac{\sigma^2(\Lambda)}{\text{det}(\Lambda)^{2/n}} G(Λ)=det(Λ)2/nσ2(Λ)​

它不再随着 α \alpha α 而变化：
G ( α Λ ) = σ 2 ( α Λ ) α 2 det ( Λ ) 2 / n = α 2 σ 2 ( Λ ) α 2 det ( Λ ) 2 / n = G ( Λ ) G(\alpha\Lambda)=\frac{\sigma^2(\alpha\Lambda)}{\alpha^2\text{det}(\Lambda)^{2/n}} =\frac{\alpha^{2}\sigma^2(\Lambda)}{\alpha^2\text{det}(\Lambda)^{2/n}}=G(\Lambda) G(αΛ)=α2det(Λ)2/nσ2(αΛ)​=α2det(Λ)2/nα2σ2(Λ)​=G(Λ)

对于 lattice 来说， G ( Λ ) G(\Lambda) G(Λ) 就是他的 Voronoi region 积分后归一化的结果。 G ( Λ ) G(\Lambda) G(Λ)越小，quantization error 也就越小。那一个自然的问题是，什么样的 lattice G ( Λ ) G(\Lambda) G(Λ) 比较小尼？

令
G n = min ⁡ Λ ∈ R n G ( Λ ) G_n=\min_{\Lambda\in\mathbb{R}^n} G(\Lambda) Gn​=Λ∈Rnmin​G(Λ)

我们想找到 G ( Λ ) G(\Lambda) G(Λ) 的最小值。首先一个结论是，对于全部整数构成的 lattice Z n \mathbb{Z}^n Zn, we have G ( Z n ) = 1 12 G(\mathbb{Z}^n)=\frac{1}{12} G(Zn)=121​, ∀   n \forall~n ∀ n. Thus,
G n ≤ 1 12 G_n\leq\frac{1}{12} Gn​≤121​

实际上我们还可以用 ball来给出一个lower bound (显然同体积下 ball 的second moment 是最小的)，因此有
1 12 ≥ G n ≥ G n ∗ > 1 2 π e \frac{1}{12}\geq G_n \geq G^*_n>\frac{1}{2\pi e} 121​≥Gn​≥Gn∗​>2πe1​

这个lower bound 是 asymptotically achievable的.

Modulation

最后我们进入本节的最后一部分内容, modulation. 这也是我们第一次讲到 Lattice 的应用。

考虑 AWGN channel
y = x + z \bm{y=x+z} y=x+z

使用 n n n 次信道，我们可以用 lattice 当做 codebook, x ∈ Λ \bm{x}\in\Lambda x∈Λ. 由于noise 是 Gaussian的， y \bm{y} y 离 x \bm{x} x 越远概率越低, 因此我们可以使用NN decoder。The error probability is then
P e ( Λ , σ 2 ) = Pr ⁡ [ z ∉ V ( Λ ) ] P_e(\Lambda,\sigma^2)=\Pr[z\notin \mathcal{V}(\Lambda)] Pe​(Λ,σ2)=Pr[z∈/​V(Λ)]

其中 σ 2 \sigma^2 σ2 是噪声的variance (per dimension). 换句话说，错误概率是噪声跑出去 Voronoi region 的概率.

假设我们有一个目标错误概率 0 < ϵ < 1 0<\epsilon<1 0<ϵ<1, 定义 σ 2 ( ϵ ) \sigma^2(\epsilon) σ2(ϵ) 为 P e ( Λ , σ 2 ) = ϵ P_e(\Lambda,\sigma^2)=\epsilon Pe​(Λ,σ2)=ϵ 时 σ 2 \sigma^2 σ2 的值。That is, 对于一个给定的lattice，每给定一个目标 P e P_e Pe​， 就有一个对应的noise variance。

我们定义

其中 μ ( Λ , P e ) \mu(\Lambda,P_e) μ(Λ,Pe​) 是不随 scaling 而变化的。即，给定一个目标 P e P_e Pe​, lattice 成比例变大变小，可容忍的最大噪声功率随着 det ( Λ ) 2 / n \text{det}(\Lambda)^{2/n} det(Λ)2/n 成比例放缩.

---

---

---

Lattices and Linear codes