（电路与系统专业论文）mimo系统的球解码算法研究.pdf

南京邮电学院硕士生毕业论文中文摘要 摘要 随着未来移动通信对数据传输速率的更高要求，m i m o 技术受到越来越普遍 的关注，而有关m i m o 技术的解码问题也受到了人们的关注。本文就针对m i m o 系统的解码问题展开了较为深入的研究。 首先，本文讨论了m i m o 系统常用的几种解码方法，给出它们的算法和性能 分析，并对不同的准则分别进行了仿真。 其次。本文介绍了两种经典的球解码算法( v b 算法和c l 算法) 。较传统的 解码算法而言，球解码算法可以在合理的复杂度范围内获得最大似然( m l ) 解 的性能。 再次，本文在介绍球解码算法常用的两种预处理方法( z f - b l a s t 排序预处理 和m m s e b l a s t 排序预处理) 的基础上提出了一种新的预处理方法( 带列交换 的q r 分解预处理) ，该方法在本身不增加太多计算量的同时可以有效降低球解码 算法的复杂度。 最后，本文提出了一种近似球解码算法。仿真结果表明，该算法能以牺牲少许 性能为代价，换取复杂度的大幅度下降。 关键词：m i m o 系统；球解码算法；预处理方法；近似球解码算法 南京邮电学院硕士生毕业论文英文摘要 w i t ht h eh i g hr e q u i r e m e n to fd a t at r a n s m i s s i o nr a t ei nf u t u r em o b i l ec o m m u n i c a t i o n s y s t e m ，m i m oh a sb e c o m et h eo n g o i n gf o c u so fr e s e a r c h , w h i c ha l s ol e a d st ot h ec o n - c 锄o fi t sd e c o d i n g am u c hd e e ph a v e s t i g a t i o no fd e c o d i n gi nm i m os y s t e mh a sb e e n d e v e l o p e di nt h i st h e s i s f i r s t l y , s e v e r a lm e t h o d so fd e c o d i n gi nm i m os y s t e mh a v e b e e nd i s c u s s e d ，i n c l u d i n g a l g o r i t h m sa n dp e r f o r m a n c ea n a l y s i s s i m u l a t i o nr e s u l t si nd i f f e r e n tc r i t e r i o na i eg i v e n r e s p e c t i v e l y s e c o n d l y , t w oc l a s s i cs p h e r ed e c o d i n ga l g o r i t h m s ( v b a n dc l ) a r ei n o d u c e d c o r n - p a r e dw i t hc o n v e n t i o n a ld e c o d i n ga l g o d t h m s ，s p h e r ed e c o d i n ga l g o r i t h m c a l ly i e l dm l d e c o d i n gw i t hr e a s o n a b l ec o m p l e x i t y t h i r d l y , t w oc o n h n o u l yu s e dp r e p r o c e s s i n gm e t h o d so fs p h e r ed e c o d i n g ( z f - b l a s t p r e p r o c e s s i n ga n dm m s e - b l a s tp r e p r o c e s s i n g ) a r ed i s c u s s e d ，b a s e do nw h i c han e w m e t h o dc a l l e dq rd e c o m p o s i t i o np r e p r o c e s s i n gw i t hc o l u m ne x c h a n g ei sp r o v i d e d t h e n e wp r e p r o c e s s i n gm e t h o dc o u l de f f e c t i v e l yr e d u c et h ec o m p l e x i t yo fs p h e r ed e c o d i n g w i t h o u ta d d i n gm u c hc o m p u t a t i o no fi t s e l f f i n a l l y , an e a ro p t i m u ma l g o n t l t mi sp r e s e n t e d s i m u l a t i o nr e s u l t ss h o wt h a tt h i sa l g o d t h mc o u l dg e ts i g n i f i c a n tr e d u c t i o ni nc o m p l e x i t yo n l yw i t hm a r g i n a ll o s si np e r f o r m a n c e k e yw o r d s ： m i m o s y s t e m ，s p h e r ed e c o d i n g ，p r e p r o c e s s i n g ，n e a ro p t i m u ma l g o r i t h m n 一 南京邮电学院学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电学院或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：日期 南京邮电学院学位论文使用授权声明 南京邮电学院、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电学院研究生部办理。 研究生签名：导师签名：i ! i ! ! ：日期： 南京邮电学院硕士生毕业论文 第一章绪论 第一章绪论 1 1 数字通信系统的框架结构 c 1 a u d es h a n n o n 曾经说过【1 l ，通信的基本问题就是在一个点准确或近似地再生 另一个点的消息。从那以后，设计能解决此问题的有效而简单的通信系统便逐渐 成为通信和信息论领域的研究中心。一方面，通信系统应设计为有效，即：能最 大限度利用所得资源；另一方面，系统在实际中须简单可行。在通信系统的设计 中，有许多数据传输的重要方面需要考虑，其中最突出的一些方面包括： 在包含信源全部信息的前提下，尽量压缩数据，并在传输后，将数据恢复为 信源； 在数据中引入冗余，用来克服信号在信道中传输时所遭受的噪声和干扰； 建立通信信道模型，对噪声进行统计描述，同时研究用于信道估计和跟踪的 技术； 设计有效恢复传输数据的接收机。 数字通信系统中数据传输的一般框图如图1 1 所示。 图1 1数字通信系统的组成部分 图1 1 中信源产生二进制信息序列，发射机通过信道，发送表征该信息的适当 ， 连续时间波形。接收机恢复被传输媒质干扰的传输信号，并对发送信号进行判 决。 图1 2 进一步详细说明了发射机。信源编码器通过压缩去除信源中的冗余，从 信源编码器输出的二进制数字序列被传送到信道编码器。信道编码器的目的是在 一1 一 南京邮电学院硕士生毕业论文 第一章绪论 二进制信息序列中适当引入一些冗余，以便接收机克服信道传输时所遭受的噪声 和干扰。数字调制器将信道编码器的输出转化为便于通信媒质传输的模拟波形 2 1 。 图1 2 发射机框图 在通过物理信道传输信息的通信系统设计中，建立一个能反映传输媒质最重要 特征的数学模型是很方便的。例如，在无线通信系统中，由于信号与环境的相互 作用( 散射、反射及折射等) ，传输信号会沿着多条路径传播。由于传播损耗和 衰弱，信号在传输过程中被衰减。其效果通常以带干扰信号和加性高斯白噪声的 多径信道为模型( 如图1 3 ) 。 图1 3 般信道模型 图1 4 进一步详细说明了接收机。图中解调器的任务是恢复作为信道编码器输 出的离散信息。为此，先将接收信号转化为基带信号( 若需要) ，再进行滤波。 滤波器的输出经采样和量化实现模拟到数字的转化，该离散序列再经一定算法恢 复为信道编码器输出。然后，信道解码器恢复作为信源编码器输出的被压缩信 号。最后，信源解码器对信源进行解压缩，恢复信源。 图1 4 接收机框图 由图1 1 所示的系统性能通常用误比特率( b e r ) 来度量。b e r 是指在接收 端错误恢复的信息比特序列的平均概率。本论文也采用该度量值来衡量算法的性 2 一 南京邮电学院硕士生毕业论文第一章绪论 能。 1 2 球解码的引入 近年来，采用多输入多输出( m i m o ) 技术的无线通信已经成为现代通信的 最重大技术突破之一，具有多根发送和接收天线的m i m o 系统可以达到很高的频 谱效率。但是，作为最优解码器的最大似然( m l ) 解码器通常由于其较高的复 杂度而在实际m i m o 系统中不可行，尤其当天线数很多或调制星座图较大时。鉴 于此，球解码作为m l 解码的替代方法被用于m i m o 系统中o 】。该解码方法在能 够达到m l 性能的同时，具有合理的复杂度。球解码算法的思想最早于1 9 8 1 年作 为在给定格( 1 a t t i c e ) 中寻求最短向量的一种方法被提出1 4 1 ，而且其复杂度是格 的维数的多项式算法 5 】。1 9 9 3 年e v i t e r b o 和j b o u t r o s 在一篇关于格码解码的论 文中最早将该算法用于通信问题【6 】。自此，球解码被认为是多用户检测c d m a 系 统m ，空时编码以及未编码多天线系统【3 】( 例如：垂直贝尔实验室分层空时结构 - - v - b l a s t ) 的近最优解码算法。 1 3 本文的主要工作及安排 m i m o 技术是未来移动通信的关键技术之一，本文针对用于m i m o 系统的球 解码方法做了一定的研究。本论文共分七章。其结构安排为：第一章绪论部分主 要介绍了通信系统的框架结构，同时引入球解码。第二章简单介绍了m i m o 系统 的发展历程，并对m i m o 系统的信道模型和信道容量都做了一定的描述。第三章 提出整数最小平方问题，并给出常用整数最小平方问题的解决方法。第四章介绍 了两种经典的球解码算法( v b 算法和c l 算法) ，详细描述了算法的基本思想， 并对复杂度和优缺点做了一定的分析。第五章首先介绍了球解码算法常用的两种 预处理方法( z f v b l a s t 排序预处理和m m s e v b l a s t 排序预处理) ，接着在它 们的基础上提出了一种新的预处理方法一带列交换的q r 分解预处理，然后通过 南京邮电学院硕士生毕业论文第一章绪论 m a t l a b 仿真比较了三种方法的性能和复杂度。第六章充分利用在接收端己知信 道状态信息( c s i ) 的条件，基于理论推导提出了一种球解码的近似算法，同时 也给出了其m a t l a b 仿真曲线。第七章得出结论，总结全文，并指出今后的研究 方向。 第二章m i m o 系统概述 2 1m i m o 系统 随着实时多媒体通信、高速i n t e r n e t 接入等数据业务的发展，提高通信系 统的速率和频带利用率已成为急待解决的问题。在无线通信系统中，提高频带利 用率的方法主要有智能天线技术、m i m o 技术、多载波调制及自适应编码调制技 术等。其中，m i m o 技术由于能有效利用多径衰落，巨大地提高系统容量和频带 利用率而成为目前国内外通信研究的热点。实验室的研究证明，采用m i m o 技术 在室内传播环境下的频谱效率可以达到2 0 4 0b i t s s h z ；而使用传统无线通信技 术在移动蜂窝中的频谱效率仅为1 5b i t s s h z ，在点到点的固定微波系统中也只 有1 0 一1 2 b i t s s h z 。 m i m o 的定义非常简单。移动通信中的m i m o 技术指的是利用多根发射天线 和多根接收天线进行无线传输的技术，而传统的通信系统是单进单出( s i s o ) 系统，基于发射分集和接收分集的多进单出( m i s o ) 方式和单进多出( s i m o ) 方式也是m i m o 的一部分，使用这种技术的无线通信系统即为m i m o 系统。 m i m o 并不是- f o 新技术，早在1 9 0 8 年马克尼就提出用m i m o 方式来抵抗无线信 道的衰落。7 0 年代有人提出将m i m o 技术用于通信系统，但是对无线移动通信 系统m i m o 技术产生巨大推动的则是9 0 年代贝尔实验室的学者们。贝尔实验室 的e t e l a t a r 和g j ，f o s c h i n i 分别于1 9 9 5 年和1 9 9 6 年独立地在他们各自的论文【9 】 和【1 0 q h 论证了理论上m i m o 信道的香农容量。同时，f o s c h i n i 还开发了用于 m i m o 系统的实际发射接收算法一贝尔实验室分层空时码( b l a s t ) 算法j 。 另一个突破性的方案是空时编码思想的提出】，它可以提高m 1 s o 和m i m o 系统 的分集增益。 m i m o 系统的系统框图如图2 1 所示。传输比特流经过空时编码形成n r 个信息 一s 一 南京邮电学院硕士生毕业论文第二章m i m o 系统概述 信 空 源 时 编 码 天 线 阵 ( 可 空 时信 解 宿 码 可 图2 1m i m o 系统的系统框图 子流。这n t 个子流由n t 个天线发射出去，经空间信道后由n r 个接收天线接收。 多天线接收端利用先进的空时编码系统处理、分开并解码这些数据子流，从而达 到最佳的效果。这n t 个子流同时发送到信道，各发射信号占用同一频带，因而并 未增加带宽。若各发射接收天线间的通道响应独立，则m i m o 系统可以创造多个 并行空间信道。通过这些并行空间信道独立地传输信息，数据传输率必然可以提 高。 2 2m i m o 信道模型 典型的m i m o 系统信道模型如图2 2 所示。 本文采用的多输入多输出( m i m o ) 信道模型可描述为： y c = 日一c + 秤c 一6 一 ( 2 1 ) 南京邮电学院硕士生毕业论文第二章m i m o 系统概述 其中， 图2 2具有”r 个发送天线和t t r 个接收天线的m i m o 信道 日= h i ，1h i ，2 - 1 ，n t h n r , th n a , 2 h n ”t ( 2 2 ) 矩阵中的元素瑰f 代表从第j 根传输天线到第f 根接收天线的衰落系数，且满足均 值为零方差为1 的独立同分布复高斯分布。；k 1 ，2 ，x r t ，】t 是n t 1 的传 输符号向量，向量中的每一个分量均为从星座图中独立选取的符号。n 。为均值为 零的独立同分布复高斯噪声变量。本文假设发射天线数和接收天线数相等，即： 礼r = n 且= r n 2 。这样，仅用一个参数即可表示信道矩阵。对于任意n t 和n 月的 推广在文献【1 2 】【1 3 中均有说明。由于本文仅考虑在实数范围内的解码算法，因此 可把实部和虚部分开，将式( 2 1 ) 等效写为： 阱隧划州引 ( 2 3 ) |l丫丫丫丫丫丫丫丫 南京邮电学院硕士生毕业论文第二章m i m o 系统概述 则等效的m 维实信道模型可表示为： y = i t x + 砧 ( 2 4 ) 此mxm 维实信道矩阵日对应于一m 2 m 2 的随机复信道矩阵。类似地，l , n 维噪声向量n 对应于每维方差为。的m 1 2 维噪声向量n 。的实部和虚部，则向量 厅满足均值为零，每维方差为2 = 靠。2 的独立高斯分布。 2 3m i m o 信道容量 系统容量是表征通信系统的最重要标志之一，它表示通信系统的最大传输 率。e t e l a t a r 和g j f o s c h i n i 已证明在理想的高斯信道下，m i m o 能巨大地提高 系统香农容量。当发射接收天线间的路径衰落相互独立且接收端已知c s i 时， m i m o 系统的容量和发射天线、接收天线个数的最小值成正比。近年来的研究结 果进一步表明：m i m o 系统的容量增益与发射接收端所能获得的信道状态信息， 信道信噪比及信道相关性密切相关。其中，信道相关性主要由散射环境、发射接 收机之间的距离、天线配置及多普勒扩展决定i t 4 。 在时不变信道中，信道容量是指信道输入输出间的最大互信息，即信道所能传 送的最大速率。在加性高斯白噪声信道中，有以下关于容量的基本结论。 当信道增益满足均值为0 ，方差为1 的复高斯分布时，s i s o 系统的容量可表 示为下式l c = l 0 9 2 ( 1 + p l h 2 ) b i t s s h z ( 2 5 ) 其中，p 表示接收端的符号信噪比，h 表示归一化的信道增益。 在发送端使用一根天线，接收端使用，l r 个天线的s i m o 无线通信系统中，系 统容量可表示为f 9 】： f i r c = l 0 9 2 ( 1 + p 时) b i t s s h z ( 2 6 ) i = l 一8 一 南京邮电学院硕士生毕业论文第二章m i m o 系统概述 其中，h l 表示从发射天线到第i 个接收天线的路径增益。从式( 2 6 ) 可以看出，采 用接收分集的系统容量随着接收天线个数的增加而呈对数增长。 同理，在发射端有n t 个天线，接收端一个天线的发射分集系统m i s o 中，假 设发射端不知道c s i ，系统容量可表示为【9 】： c = l 。9 2 ( 1 + m 。p 曲i h l m i t s 枷z ( 2 7 ) 从式( 2 7 ) 可以看出，系统容量随发射天线个数的增加而呈对数增长。 在时变信道中，信道容量有多种定义方式，主要取决于发射接收机所能获得的 c s i 或信道分布信息( c d i ) 以及信道容量的度量所基于的不同准则一是在所有 信道状态下的信息速率的均值还是在维持恒定的信息速率时就中断概率而言的容 量。本文对此不再详述。 9 南京邮电学院硕士生毕业论文第三章整数最小平方问题 第三章整数最小平方问题 3 1 整数最小平方问题 对于式( 2 4 ) ，m l 准则使在发射为工的条件下，接收到y 的概率最大，即满足 下式： m a x p y l z b l x ) ( 3 1 ) 式( 3 1 ) 的最优化须对星座图内所有的点进行。假设采用噪声为加性高斯白噪声( a w g n ) ，则已知工的y 的条件概率密度函数为： p , l x 0 , 1 ，) = 瓣1 e 哼 ( 3 2 ) 因此，式( 3 2 ) 条件概率的最大化问题等效于以下非线性最小化问题，称为整数最 小平方问题： 呼n i ! y - x x l l 2 ( 3 - 3 ) 从几何意义上来说，整数最小平方问题等效于最近格点搜索问题，其中的给定 点不是空间内任意点，而是被统计特性已知的噪声干扰的格内的点。因此可将搜 索格内最近点的方法用于整数最小平方问题。最近格点搜索又可分为以下无限和 有限格点情况。 3 1 1 无限格点情况 给定向量ye 冗“，矩阵h 冗“”，及m 维整型格z ”，寻找使下式最小化的向 戡z “： 础m i n 。i b ，一胍lj 2 ( 3 4 ) 式( 3 4 ) 的最小化问题是在m 维无限空间内搜索向量工。例如，寻找使用全球定位 一l o 南京邮电学院硕士生毕业论文 第三章整数最小平方问题 系统( g p s ) 的点坐标。 3 1 2 有限格点情况 在实际数字通信的应用中，对传输信号的功率限制就意谓着搜索空间是无 限格点的子集，即：口cz “。那么，式( 3 4 ) 转化为给定向量y 冗“和矩阵 h 冗“”，在r n 维整型格z “的有限子集口内，寻找使下式最小化的向量 z 口： ，艘。i l y 一酬1 2 ( 3 5 ) 从几何图形来看，式( 3 4 ) 和式( 3 5 ) 就是在集合内寻找距离接收点y 的欧氏距离最近 的格点，如图3 1 。事实上，无论在最坏意义彻还是一般意义 1 8 l 下，m l 解都需要 搜索集合内所有可能的点，因此其计算复杂度与集合大小成指数关系。 图3 1 整数最小平方问题几何示意图 3 2 整数最小平方问题的解决方法 下面，本文将回顾可用于整数最小平方问题的几种常用方法，包括：启发式算 法，缩小格方法及准确方法。 3 2 1 启发式算法 通信中经常可以碰到整数最小平方问题，但是，求解m l 解的复杂度相当高， 搜索空间随发射信号符号集的长度和每维符号的比特数呈指数级增长。所以实际 系统常采用具有合理计算复杂度的近似或启发式算法。其又可归纳为以下几类： 南京邮电学院硕士生毕业论文第三章整数最小平方问题 3 2 1 1 迪零法( z e r o f o r c i n g ) 一种可简单而直接得到估计值i 的方法，先得到下式： y = h - l y = z + h 一1 n 将此向量量化到星座图上最近的点，可得： 童= 们z ( 3 6 ) ( 3 7 ) 由于各维信号互不相关，因此每一维可独立进行量化，即： ) ， 2 = 畦】z ，【) ，m 】三) 。此方法的复杂度主要取决于求式( 3 1 6 ) 中矩阵h 的广义逆。 3 2 i 2 最小均方误差法( m m s e ) 如果信道矩阵日的某些列近于平行，甚至线性相关( 日是奇异阵) ，那么根 据以上迫零法，相应的噪声项在与日- 1 相乘后将被显著扩大，甚至变为无穷大。 因此，为了避免这种情况的发生，可以考虑采用最小均方误差法。 此方法根据式( 3 8 ) ，通过寻找矩阵雪来平衡干扰和噪声增强： 膏= a r g m i n e e l i f y x l l 2 ) 然后，将y = 西各维量化到离星座图最近的点。 在求户的过程中，首先根据正交性原理，有： e ( 西一工沙t ) = 0 且，西。：= e l = t 】，中。= e w w t 孔e x w t = 0 ，因此将式( 3 9 ) 展开得 ( 3 8 ) ( 3 9 ) 砘o 亨丁) 一e x y t ) = 声( 日西。日t + 西。) 一西z x h r = 0 ( 3 1 0 ) 南京邮电学院硕士生毕业论文第三章整数最小平方问题 经整理，得： 雪= t 卫= = h t ( h g p 。h t + 垂。) 一1 = ( 垂。- z 1 + 日t 圣：乞日) 一1 日t v 。- 。1 = ( h r u + 舞矿1 矿 = ( h t h + 甜) 一1 点，( 3 1 1 ) 其中，垂。和垂。分别用口弘和盯：j 代入。 3 2 1 3 零化和抵消( n u l l i n ga n dc a n c e l l i n g ) 下述方法中，只将上述z f 及m m s e 法用于其中一维，比如首先用于最后一维 的估计。然后，假设这一维的值已知，并从接收信号中将其影响消除，从而得 到一个剩余m 一1 维的解码问题。重复此过程求得一1 ，主m 一2 直到曼- 。在通信 中，该方法也称为判决反馈均衡( d f e ) 。 为方便起见，信道矩阵j 5 r 可表示为h = 匹1h 2 盘。】的列向量形式。 z f - d f e 算法可描述为： y 1 ：2 y f o rk = 0t om 一1 2 。一k ：= d e c i s i o n ( 日m k e m 一女】一l y + 1 ) y k + 2 = y k + 1 一h m 一 一k e n d 其中，日m k = 隆lh 2 h m 一 ，e m - k 是一个第m k 维为1 ，其它各维 为0 的( m k ) x1 的列向量。 m m s e d f e 算法可描述为： j ，1 ：2 y 一1 3 南京邮电学院硕士生毕业论文 第三章整数最小平方问题 f o r 七= 0t om 一1 一：= d e c i s i o n ( h t h + 4 1 ) n r y k + 1 ) j ，+ 2 = y k + 1 一鱼m 一女主m k e n d 其中各参数同前。 3 2 1 4 带排序的零化和抵消( n u l l i n ga n dc a n c e l l i n gw i t ho r d e r i n g ) 上述归零和抵消算法中，对于未判决各维，均假设先前的判决为正确的。然 而，这种做法可能导致错误传播：若判决错误，则会对剩余未判决各维信号 主。一，一2 等产生负面影响。为了使这种错误传播的可能性最小，可以考虑对 各维信号从“最强”到“最弱”依次执行归零和抵消算法。由于此思想最早用于 b l a s t 结构，因此也称为b l a s t 思想。根据不同的准则，带排序的归零和抵消 算法又可分为z f - b l a s t 和m m s e b l a s t 。 z f b l a s t 算法： 令y 1 ：= y ，则与式( 3 6 ) 类似有： y = h b 1 = 工+ h - 1 n f 3 1 2 ) 从式( 3 1 2 ) 可看出，向量y 中，经矩阵日_ 1 的噪声增强最小的分量被正确检测的可 能性最大。由于噪声n 被假定为独立同分布且方差相同，因此该分量对应于具有 “最短长度”( 最小欧几里德范数) 的矩阵日- 1 的行。所以，该算法首先寻找具 有最小欧几里德范数的矩阵日q 的行，并将矩阵日的相应列与最后一列交换，相 应分量与最后一维分量交换。然后对最后一维分量作判决，再从接收信号中除去 其带来的影响，即：使得y 2 = y 1 一血。主。继续在矩阵日1 的前r n 一1 行寻找具有 最小欧几里德范数的行，并对相应分量做判决，直到所有分量判决完毕为止。 由于具有最小欧几里德范数的矩阵日_ 1 的行对应于具有最大欧几里德范数的 一借堂舢 南京邮电学院硕士生毕业论文第三章整数最小平方问题 矩阵日的列，所以，算法在实现时是按照矩阵日的列由小到大的顺序排列的。 其算法可描述如下： y 1 ：2 y f o r 七= 0t om 一1 寻找j = a x g m a x i l l h i l 2 ，i = 1 ，m k 对陋l 一 进行重排，使得而等于x m k 匿。h m - k 亦做相应重排 主m 一：= d e c i s i o n ( h 某+ 1 ) y k + 2 = j ，詹+ 1 一色n 一 一k e n d 其中，l i l 某k 表示h - 1 的第m 行。 m m s e b l a s t 算法： 此算法中，认为具有最小误差方差的向量为最强信号，按此顺序对发送信号各 分量依次排序。 如前述m m s e 算法中所示，有： 西。= e x x t 】，圣。= e w w t 】，e 陋1 ，t = o ， 向量x 的线性最小均方估计为： 童= ( h t h + 0 1 ) 一1 日0 则估计误差工一主的协方差矩阵为： f 3 1 3 ) p 垒e ( x 一主) 伍一童) t = ( 日t 日+ n ，) 一1 ( 3 1 4 ) 显然，对应最小误差方差的墨是信号工中最强的分量，即：使只i 最小的分量。 1 5 一 南京邮电学院硕士生毕业论文 第三章整数最小平方问题 假设将最强信号重置于第m 维，则可得信号一个较准确的估计值= 二_ ，再利用此估计值对剩余m 1 个信号进行估计，将问题缩减为下式： y 一自b n = 日m 一1 x m 一1 + n 其中，日。一1 的定义同上，工。一l 的定义为： 其算法可描述如下： 工m 一1 = x m - 1 ( 3 1 5 ) ( 3 1 6 ) y l ：2 y f o r = 0t om 一1 拙( m 一女) = ( 砩- k 一女+ 以) 一1 且j = a r g m i n l 毋- k ) ) ， i = 1 ，m 一后 对b 1 一k 】进行重排，使得却等于工。一k 阻盘。一k 1 亦做相应重排 主m 一：= d e c i s i o n ( h m lk y k + 1 ) y k + 2 = y + 1 一h - - m k t n k e n d 本文分别在z f 准则和m m s e 准则下对上述算法进行了仿真。仿真中采用4 q a m 调制方式，收发天线数 t = n 冗= 4 。其各自的性能仿真结果如图3 2 和 图3 3 所示。 通过仿真结果可见，正如上述理论分析所示，在同一种准则下，b l a s t 的性 能最好，其次是d e f ，最后是直接采用准则的方法。 一1 6 一 南京邮电学院硕士生毕业论文第三章整数最小平方问题 图3 2z f 准则下4 发4 收，4 q a m 性能曲线 3 2 2 格约化方法 对于前述各启发式算法，一般仅在信道矩阵日的各列为正交的情况下所得的 解才正确。然而，实际矩阵日的各列并不正交。通过q r 分解等方法对矩阵日各 列正交化通常会破坏格结构( 若x 是整型输入，则r x 不一定是整型输入) 。因 此，一种可行的方法是：寻找可逆m m 矩阵r ，该r 和r - 1 均为整型输入( 从 而保护了格结构) ，且矩阵g = 日r 尽可能正交。找到此r 后，式( 3 4 ) 变为： m i nl l y 一6 t l l 2 t e z m 。 ( 3 1 7 ) 在此基础上再利用前述各启发式算法，并设定t = t x 。但是，寻找满足条件的 f 本身就是非多项式复杂度的。用a 代表矩阵h 产生的格，典型的用于a 的格约 化基包括m i n k o w s k i 2 1 1 和k o r k i n e z o l o t a r e v 2 2 i 2 3 l 。 3 2 2 1m i n k o w s k i 约化 基g = 睦1 9 - 2 曼m 】是m i n k o w s k i 约化基，若满足： 一1 7 一 南京邮电学院硕士生毕业论文 第三章整数最小平方问题 1 0 誊1 0 - - 2 1 矿 - m m s t = + m 惦e d f e _ 一m m s e b l 耵 6 9 1 21 s1 82 12 42 73 0 s n r ( d b ) 图3 3i d v i s e 准则下4 发4 收，4 q a m 性能曲线 g ，是格a 中最短非零向量； 对每个七= 2 ，m ，邑是a 中最短非零向量，因此选1 邑) 可被扩展为a 的基。 约化基g 显然包含a 中最短非零向量g ，。但是，在格中寻找最短非零向量是 非多项式复杂度的，且目前没有多项式复杂度的算法可找到m i n k o w s k i 约化基。 3 2 2 2k o r k i a e - z o l o t a r e v 约化 基g = 睦l 邑曼m 是k o r k i n e z o l o t a r e v 约化基，若满足： g ，是格a 中最短非零向量： 对每个k = 2 ，m ，定义a k 为由g 一1 = 睦l 邑一l 】扩展的( 一1 ) 维子空 间，用a 士代表g “内a k 的正交补。另外，用& ( a ) 代表a 在a 士上的正交投 影n & ( & ) 是鼠( a ) 中的最短非零向量； 对l 七 j m ，l ( 鼠( 邑) ，& 呜) ) i - - - 钏& ( 邑) 怦且岛( 邑) 2 曼七a 因此，在此方法中，基向量邑的选择是基于其在由g 一1 = 睦1 邑一l 】扩 一1 r 一 南京邮电学院硕士生毕业论文第三章整数最小平方问题 展的正交补的长度。由文献【2 4 1 可知，每个格至少具有一个k o r k i n e z o l o t a r e v 约化生成矩阵。同m i n k o w s k i 约化基一样，没有已知的多项式时间算法可找到 k o r k i n e z o l o t a r e v 约化基。因而，需要一种可以在多项式时间内执行的格约化技 术，即使适当降低正交化限制。其中，最著名的是l e n s t r a - l e n s t r a l o v a s z 约化。 3 2 2 3l e n s t r a - l e n s t r a l o v a s z ( l l l ) 约化 基g = 睦1 邑曼。】是u 上约化基，若满足： i 脚l ，1 j i m ； i l 酊+ 胁j l h s - 1 1 1 2 印| l 自1 i l2 ( 1 i m ) 。 其中：p 玎= 糍， h + = 陟蟛醵 是由h 和参数叩( ，1 ) 产生的g r a m - s c h m i d t 正交基a 无论是m i n k o w s k j 还是k o r k i n - z o l o t a m v 约化，其产生的基均较l l l 正交，但 是u 工的优点在于，有多项式时间算法可以找到l l l 约化基。其步骤如下： 对向量盘l ，如，k 施行g r a m - s c h m i d t 正交化过程，以得到向量 醚，醚，鳞： 蟛一毛一霎舔蚴一嘶卅 向量塑l ，h 2 ，b 包含由塑1 ，如，k 扩展的子空问的正交基。式( 3 1 8 ) 显 然可见，任一向量盘 可由盘。，如，盘m 的线性组合表示： 妨= 心i 蟛 ( 3 1 9 ) 其中，脚i = 篙斋，i = l ，2 ，j l ，且p 打= 1 。 对于j = 1 ，2 ，g ，i = 1 ，2 ，j 一1 ，用毛一f 脚d 毛代替毛，坳l j 是最 接近助f 的整数值。根据式( 3 1 8 ) 和式( 3 1 9 ) 的新h _ j 值，更新蟛和脚i 的值。 南京邮电学院硕士生毕业论文第三章整数最小平方问题 若下标j = 1 ，g 不满足i i 蟛+ 1 + 卢( 什) 骘1 1 2 i i i 蟛1 1 2 ，则交换h j 和玛+ 。 ，并返回第一步，反之则停止。 格约化方法有助于解式( 3 4 ) ，即无限格点情况，但是对式( 3 5 ) 所示的有限格点 情况却没有用，原因是格转换矩阵t 常会破坏子集dcz m 的属性。由于通信系 统中通常关注有限子集的问题，因此，本文后面不考虑格约化方法。 3 2 3 准确方法 对本文前面描述的各启发式算法，其性能的仿真如图3 3 和图3 2 所示。从图中 可见，在同种规则下的诸多启发式算法中，b l a s t 的性能是最好的，相同方法 在m m s e 准则下的又优于z f 准则。但是，即使是m m s e b l a s t 算法，其性能 也远次于最优解 3 1 。因此，有必要研究可以达到m l 性能并具有合理复杂度的解 码算法。这样的算法主要包括两大分支：k a n n a n 【1 6 】算法和f i n c k e - p o h s t 吲算法。 k a n n a n 算法仅对一特定平行四边形内的格点进行搜索，通常用于理论研究渐进复 杂度，而f i n c k e p o h s t 算法则仅对一特定球内格点进行搜索，更倾向于作为实际实 施的工具。本文后面将详细讨论f i n c k e p o h s t 算法及在其基础上扩展的球解码算 法。 一2 0 南京邮电学院硕士生毕业论文第四章经典球解码算法 4 1 信号星座 第四章经典球解码算法 可经信道传输的所有可能的符号点的集合被称之为星座图。星座图的设计通常 需对两个对立的要求取折中，即：一方面希望星座图内的点彼此间隔越大越好， 而另一方面，又希望传输符号的能量越低越好。本文采用m 进制正交振幅调制( q a m ) 星座图( 1 9 】，如图4 1 所示。4q a m 星座的平均符号能量为2 ，发射信号工。 1 6 - q a m i4 - q a m ； j 1 i i l 图4 i4 q a m 和1 6 q a m 星座图 各维的实部和虚部取值集合为q 4 = 一1 ，1 ：1 6 q a m 星座的平均符号能量为1 0 ， 发射信号x 。各维的实部和虚部取值集合为q 1 6 = - 3 ，一1 ，1 ，3 ) 。对于mq a m 星 座，x q 器。但是，需要说明的是，本论文所涉及的方法并不适用于所有星座。 例如在单位平均符号能量的8p s k 中，取值集合q 8 = 一1 ，一1 j ，0 ，1 、，压，1 ) ， 而集合中任意取的两个值组成的复信号并不一定是8p s k 星座图中的点，比如信 号1 一j 。参考文献( 1 5 】中的复球解码算法解决了此问题，本文不再傲讨论。 一2 l 一 南京邮电学院硕士生毕业论文第四章经典球解码算法 4 2v b 球解码算法 4 2 1 算法基本思想 1 9 9 9 年，e v i t e r b o 和j b o u t r o s 二人在文献【2 0 】中提出通用的格码解码算法， v b 算法由此而得名。该球解码算法的基本思想是：首先给定一个初始球半径 厢，在以接收点y = 却为球心、橱为半径的球内进行搜索。如果球内不 存在向量x 满足f p h x l l 2 g ，则放大球半径，在放大的球内继续搜索；反 之，若找到了这样的向量，则将球半径缩小为新找到的向量距离球心的距离， 即：c = ib ，一h x l l 2 ，并继续在缩小后的球内进行下一轮搜索，寻找向量x 满足 i i ) i 一三h 1 1 2 g 。如此下去，直到球内不存在经日变换后满足条件的q m 中的向 量为止，最后一次用于缩小球半径的向量作为最终的解码结果输出。 假设c s i 在接收端已知，那么按m l 准则，解码即为求向量h 的优化问题： a r g r n i n x 口嚣i p 一丑七0 2 a r g m i n x q r y h x ) t 0 一h x ) = a r g m i n z q 嚣( 日p h x ) t ( h p h x ) = a r g n f m x q 嚣( p 一工) t h t h ( p 一工) 对矩阵日做q r 分解得到h = q r ，其中，q 是正交阵， 足是上三角阵。令e = p 一“，一并代入上式得： l y h u l l 2 =e t ( 鲫) r q r c ( 置) r q r q r e ( 4 1 ) 即满足：q r q = j = 脾s i l 2 = 霎( 妻勺勺) 2 cz，1 = ( 懈汁勺勺) ( 4 2 ) = 、 j = i + l 7 塑夏坚皇堂堕堡圭兰望些笙茎箜四童丝壅堡堡塑簦鲨 另外，对上式做替换q i i = 吃，i = 1 ，m 且q 玎= r i j r l l ，i = 1 ，m ，j = i + 1 ，m ，则式( 4 2 ) 可以写成： 扣一日h 酽= i 吼；，一。 2 g ( 4 s ) 扣一日h | | 2 = 吼 g ( 4 _ 3 = l ( e l + 7 = 妻中1q , i c i ) i - 算法从最后一维开始，从后往前解，由此首先得到第m 维的取值范围： + p 仇1sh 。f ll + p r o i ( 4 4 ) j 其中，m 取大于x 的最小整数值，h 取小于x 的最大整数值。 将其上、下边界值分别对应到具体的星座q ；【；，则上式又可写为： 眯 - 压+ 压+ 星座q 器在式中的意义表示分量取位于上下界之间，集合q 嚣内的整数值。 ( 4 5 ) 依次类推，根据前m i 个分量( u m ，u m - - i ，地+ 1 ) 的取值，得到第i 维分量 的取值范围： 蹦i 其中， a ( “骅1 ) = j i e j m , + 1 乌甜q1 ， + 1 吼，勺f 。 玩( “嚣。) = a i ( 识1 ) ，口；( 啦。) ，口蜀 ( 4 6 ) 瓜焉i f 丽2 地+ l 瓜焉i f 丽垤+ 如此下去，直到第1 维分量的范围被确定。 式( 4 6 ) 所示星座点的集合称为该解码分量的候选符号集。v b 算法采用p o h s t 规则对候选符号集内的元素按从小到大的自然顺序扩展，即：若不考虑星座，按 也( “嚣1 ) ，a i ( u 嚣1 ) + 1 ，毋( “嚣1 ) 的顺序选取。每选取第i 级候选符号集内的一个 元素，就可以