科斯塔斯阵列有限域声纳和最难听的音乐

假如咱们能创造出一段没有任何重复的音乐，没有旋律，没有形式，没有份额。那么得到的便是一首十分刺耳的音乐。

撰文 | 蒋迅

从视频https://v.qq.com/x/page/i06754hidxr.html中，咱们看到了陈奕迅把歌唱到了最刺耳的地步。陈奕迅能做到这一点真的是不简略。但对数学家来说，创造出一个最刺耳的歌曲并不是特别难的作业。今日我就来讲讲数学家是怎样做到的。不过先要从一个看似无关的数学游戏说起。由此咱们介绍数学在通讯科学中的一个运用，然后以最刺耳的音乐完毕本文。

主张在阅览这一篇之前，先阅览笔者对哥隆尺的介绍。这样或许对本文的思维有些协助。不过，本文并不要求读者具有哥隆尺的常识。

01 科斯塔斯阵列的界说

咱们考虑在平面上的n×n的网格。在这些网格中，咱们将放入 n 个圆点，使得在每一行和每一列上都只需一个圆点。咱们能够用 0 和 1 来替代这些点：有圆点的方格上咱们放入 1，不然就放入 0。满意上述描绘的最简略的网格便是对角网格。下面是两个

表 1

再看一个非对角网格。

表 2

咱们期望运用这种矩阵的表达形式，但咱们并不要求读者有矩阵的常识。所以咱们甘愿把它叫作阵列。

关于上面的对角网格来说，四个圆点的坐标是：(1,1),(2,2),(3,3),(4,4)；另一个非对角的网格的圆点坐标则是 (3,1),(4,2),(2,3),(1,4)。用矩阵的表明法，上面两个比方别离是

在矩阵言语里，这样的矩阵叫作置换矩阵，因为每一个这样的矩阵都能够经过一系列行与行之间的交换而终究变成对角矩阵。

作为置换矩阵，咱们也能够把它写成数学上的“摆放”。比方上面的对角矩阵能够写成一个普通摆放：[1,2,3,4]；非对角矩阵能够写成 [3,4,2,1]，它是普通摆放 [1,2,3,4] 的一个摆放。像咱们介绍的哥隆尺，咱们能够从摆放的表明来结构倒三角。开端科斯塔斯便是从这个视点来结构开端的几个科斯塔斯阵列的。咱们不深化评论。

假如咱们把这儿的网格比作刻度尺的话，那么科斯塔斯阵列就能够比作哥隆尺。所以咱们能够把科斯塔斯阵列看作是哥隆尺在二维的推行。

02 科斯塔斯阵列的一个等价界说

科斯塔斯阵列有一个等价的界说，而这个界说能协助咱们了解科斯塔斯阵列在运用中的含义。为此，咱们对阵列A扩展如下：

也便是将阵列A往四个方向用 0 无限延伸。咱们称之为A的扩展阵列。咱们界说阵列A的非周期自相关函数（autocorrelation function）为

在本节的最终，咱们趁便界说两个n×n阵列A和B的互相关函数（cross-correlation function）：

03 科斯塔斯和已知的一些科斯塔斯阵列

图 1. 约翰 科斯塔斯

约翰 科斯塔斯（JohnP. Costas）是美国电子工程师。1947 年，他从普渡大学结业。这时正值第二次世界大战。他加入了美国水兵，成了一名雷达军官。后来他进入麻省理工学院，研讨搅扰滤波和线性体系编码。在校园里，他得到了美国运用数学家诺伯特 维纳（NorbertWiener）、意裔美籍核算机科学家罗伯特 法诺（Robert Mario Fano）、美国电子工程学家杰罗姆 威斯纳（Jerome Bert Wiesner）和我国现代前期电机工程学家李郁荣。从 1951 年开端，他受雇于通用电气公司。1980 时代初，他转到 Cogent Systems 公司直到退休。科斯塔斯最闻名的效果还不是科斯塔斯阵列，而是他在 1950 时代发明的对现代数字通讯发生深远影响的科斯塔斯循环（Costasloop）。进入 1960 时代后，他处理了声纳体系作用欠安的问题。他的解便是本文的科斯塔斯阵列。咱们将在稍后做具体介绍。

找到科斯塔斯阵列比找到哥隆尺相对简略一些，因为在二维上自由度比一维大一些。科斯塔斯在 1975 年用手在一张纸上凑出了一个 12×12 的科斯塔斯阵列。因为他无法找到更大的比方，他置疑对n > 12 或许不存在这样的阵列。但后来人们发现了一些算法，能够得到恣意大的科斯塔斯阵列。下面的表格给出前 36 阶的科斯塔斯阵列的数量表。

表3. 科斯塔斯阵列一览表

现在，从n = 1 到 29 的一切科斯塔斯阵列都现已找到。在 29 之后还没有一个n得到了悉数科斯塔斯阵列。咱们用斜体字表明咱们得到的是科斯塔斯阵列的数目的下限。特别让人们意外的是，至今人们还没有找到n= 32 和 33 时哪怕一个科斯塔斯阵列。人们也无法证明不存在n = 32 和 33 时的科斯塔斯阵列。乃至有人预算说，当n = 32 时，用现在已知的算法和现有的设备，找到悉数科斯塔斯阵列需求 45000 年的核算机时刻！所以至今是否对恣意的正整数n来说都存在科斯塔斯阵列仍是一个未解之谜。人们依然在尽力寻觅新的算法。咱们不计划包括悉数这些算法，而仅仅介绍一下最早的两个算法。这两个结构法都有很强的数学布景。

04 有限域和原根

这儿咱们要提到的数学布景有一段悲催的故事。这个故事始于 200 年前的法国。一位年轻人伽罗瓦（Evariste Galois）为了处理困扰五次多项式的根式解问题另辟奇径，搞出来一个一切其时的大数学家都无法了解的思路。政治上，他激烈支撑共和，遭到保皇实力的镇压。更独特的是，在他 21 岁的时分为一位女子与人决战。决战前，他匆忙写下了他的数学效果，然后托付他的朋友有必要找到出书的当地。他的稿子没有得到高斯（JohannKarl Friedrich Gauss）、雅可比（Carl Gustav Jacob Jacobi）的赏识。所幸的是，这个稿子后来被刘维尔（Joseph Liouville）的必定，总算开展成为了数学界的丰碑“伽罗瓦理论”。他的故事现已呈现许多数学科普著作中。咱们后边会看到卡斯塔斯阵列在通讯中的运用。估量伽罗瓦没有想到的是，他的数学效果能在二百多年后运用到通讯范畴。

在数学上，实数的整体构成一个“域”。所谓域，便是一个代数结构，在它里边能够进行加、减、乘和除（除数不为零）运算。比方说两个实数相加仍是实数，两个实数相除也仍是实数，只需除数不是零。运算成果依然保留在这个代数结构里。咱们看到，域的概念是数域以及四则运算的推行。

实数域是一个无限域。但并不是一切的域都是无限的。有限域也被称为伽罗瓦域（Galois field），很明显是为了留念这位巨大的法国数学家伽罗瓦。有限域便是具有加减乘除运算的包括有限个元素的域。有限域最常见的比方是当p为素数时，整数对p取模。咱们把它记为 GF(p)。它的元素能够用 0,…,p-1 表明。咱们假定对这些元素做四则运算时在取模的含义下进行。也便是说，一旦一个运算成果达到了p，就将这个数归零；运算成果超过了p时就把这个数减去p，直到其成果落入到 0 到 p-1 的规模之内。这种运算叫作模运算（mod），一般用“≡”表明，可是在代数学里也会用“=”表明，只需不会引起混杂。以 GF(7) 为例，它的元素为 0,…, 6。咱们有 1 + 4 ≡ 5(mod 7)，4 + 5 = 9 ≡ 2(mod 7)。有了模运算后，咱们就能够引进欧拉函数的概念。界说欧拉函数φ(p) 为与p互素并小于或等于p的那些正整数的个数。在咱们考虑的比方中，p为素数，所以总是有φ(p)=p-1。留意欧拉函数并不仅仅对素数界说的。在后边的科斯塔斯阵列的算法中也会用到更一般的整数的欧拉函数。

而当基数为 2 时，2^3= 8 ≡ 1(mod 7)，可是指数 3

现在咱们能够介绍科斯塔斯阵列的结构法了。至今科斯塔斯阵列的结构法依然是一个活泼的科研范畴。但限于篇幅，咱们只介绍两个最早呈现的办法：卫曲结构法和蓝波-哥伦布结构法。

05 劳埃德 卫曲和卫曲结构法

图2. 劳埃德 卫曲

卫曲阵列是最早的一个结构办法。其实，这个办法是由美国数学家和编码专家埃德加 吉尔伯特（Edgar Gilbert）在 1965 年，即科斯塔斯发现科斯塔斯阵列的一同发现的。当然这个时分他并不知道科斯塔斯的作业。所以他的起点是不同的：拉丁方阵 (Latin square)。惋惜的是，科斯塔斯发现了科斯塔斯阵列可是没有开发一套核算办法，而吉尔伯特规划了一个奇妙的办法却不知道科斯塔斯阵列。因为他们两人没有呈现交集而使得吉尔伯特的作业被埋没了。一直到 1982 年，吉尔伯特的结构法才从头被美国运用数学家和信息科学家劳埃德 卫曲（Lloyd R. Welch）发现。

卫曲于 1951 年结业于伊利诺伊大学厄巴纳-香槟分校数学系，又在 1958 年从加州理工学院取得数学博士学位。他的博士论文的标题是：卷积积分的排序和最大化。比较自相关函数和卷积，咱们能够感觉到他在读书的时分就现已为他今后的作业铺垫了路途。结业后他在喷气推动实验室、国防剖析研讨所和南加州大学作业。卫曲的首要奉献是寻觅隐马尔可夫模型的不知道参数的鲍姆-卫曲算法（Baum-Welch algorithm）和一种用于高效地解码 BCH 码与里德-所罗门码的伯利坎普－卫曲算法（Berlekamp-Welch algorithm）。

卫曲并没有投入到科斯塔斯阵列的研讨。本来科斯塔斯在用纸笔重复凑答案失利之后，他转向哥伦布求救。这是 1970 时代后期的作业。哥伦布一方面告知科斯塔斯，这个问题曾经还没有人研讨过（其实他是不知道吉尔伯特的作业）；他一同向他在南加州大学的搭档和协作者卫曲问询。这两个人早就在算法学上长时刻协作。早在 1968 年，他们就一同提出了在编码理论里至今未处理的“哥伦布-卫曲”猜想，并且这方面的作业就与伽罗瓦域严密相关。卫曲意识到了科斯塔斯的问题能够用伽罗瓦域的成果来做。这便是卫曲结构法。1982 年，哥伦布在和赫伯特 泰勒合写的一篇关于科斯塔斯阵列的评述中初次介绍了这个算法。随后哥伦布给出了严厉的证明。

上面咱们举了一个p= 7 比方。咱们现已看到 GF(7) 的原根g= 3，并且咱们得到了一个由模余数构成的置换 3, 2, 6, 4, 5, 1。能够验证相应的 6 阶阵列A便是：

明显，前面的界说是当c= 0 时的特例。假如c= 1，那么能够看到

而这正是咱们预期的阵列 [3 2 6 4 5 1]。这两阵列的差异仅仅是在水平方向的一个平移。所以从实质上说它们是等价的。

06 蓝波-哥伦布结构法

第二个前期科斯塔斯阵列结构法也是从有限域动身的。这便是哥伦布介绍的蓝波-哥伦布结构法（Lempel-Golomb construction）。

亚伯拉罕 蓝波（Abraham Lempel）出生于波兰。他别离于 1963 年、1965 年和 1967 年从以色列理工学院取得学士、硕士和博士学位。然后，他作为研讨助理前往南加州大学。在那里开端了与哥伦布的长时刻协作。1969 年，他加入了位於马萨诸塞州萨德伯里的斯佩里兰德研讨中心任研讨员。1971 年，他回到以色列理工学院，在那里担任核算机科学教授直到退休。他一同还担任 IBM 沃森研讨中心的职务。他最闻名的作业是在无损数据压缩算法的两个算法“LZ77 与 LZ78”，并且这个作业也是根据有限域的性质。在那段时刻里，他在有限域方面有许多研讨。趁便提一句，还有一位叫作泰瑞 卫曲（Terry Welch）的美国核算机学家把无损数据压缩算法做了改善，这个新算法称为“蓝波-立夫-卫曲（Lempel-Ziv-Welch）编码法”。

蓝波的算法也是哥伦布与泰勒 1982 年的同一篇论文中首要宣布的。稍后哥伦布完成了证明。哥伦布和泰勒介绍的是一个推行了的蓝波结构法。咱们在这儿也先介绍蓝波-哥伦布结构法，然后作为一个特例给出蓝波结构法。

当φ=ρ时便是蓝波提出的原始景象。

让咱们看一个比方：令p= 11,n= 1，然后q=p^n= 11。核算可知φ= 2，ρ= 7 是 GF(11) 的两个原根：

所以，运用蓝波-哥伦布结构法，咱们能够得到下面的置换阵列：

表 4

咱们把核算留给读者。

07 科斯塔斯阵列在声纳的运用

前面咱们说过，科斯塔斯是在研讨声纳时发现的科斯塔斯阵列的。现在咱们就来谈谈声纳与科斯塔斯阵列的联络。

故事仍是从科斯塔斯开端。从麻省理工大学博士结业后，他受命为水兵处理用声纳侦办潜艇功率不高的问题。由於电磁波在水中衰减的速率十分的高，无法做为侦测的信号来历，以声波勘探水面下的人工物体成为运用最广泛的手法。无论是潜艇或者是水面船舶，都使用这项技能的衍生体系，勘探水底下的物体，或者是以其作为导航的根据。声纳的作业原理是它宣布音响信号，借由这个信号触摸物体后反射回来声波的改变，做为核算这个物体的相对方位与间隔的材料。这种办法便是使用了多普勒效应。

多普勒效应（Doppler effect）是波源和观察者有相对运动时，观察者接遭到波的频率与波源宣布的频率并不相同的现象。或许你早就留意到，远方急驶过来的火车鸣笛声变得尖细（即频率变高，波长变短），而离咱们而去的火车鸣笛声变得消沉（即频率变低，波长变长）。这便是多普勒效应的现象。这一现象开端是由奥地利物理学家多普勒（Christian Doppler）1842 年发现的。

在实践运用中，人们一般是在接连的几个相同的时刻段里宣布不同频率的声波系列，然后搜集反射回来的声波。当收到的一个从移动物体反射回来的回音时，这个体系会与它宣布的音频系列各个时刻和频率上的平移做比较，从中找到与这个反射回来的信号高度符合的那个时刻和频率的平移。从时刻的平移人们能够核算出物体的间隔规模；从频率的改变，人们能够核算出物体移动的速度。

假如没有任何杂音的话，这个成果应该就很好了。但在实践运用中杂音是避免不了的。所以咱们有必要能够区别布景杂音和方针物体反射的回音。为此，咱们有必要将收到的信号与发射信号的一切 (2n-1)(2n-1) 个组合逐个比较，并期望在这些组合中只需那个对应于方针物体的方位和速度的平移与其有较高的互相关性。因而，在规划这组频率信号时，咱们有必要让咱们置换阵列使得其一切的非普通位移（即零位移）都与其自身具有低相关性。

咱们期望以上的评论现已把科斯塔斯的思维展现出来了。科斯塔斯阵列在通讯上的研讨至今活泼，在我国也是相同。咱们不计划更深化地从电子工程的视点谈科斯塔斯阵列是怎么施行的。可是想指出我国学者在这方面也有一些作业。咱们在参考文献里引用了几篇，比方周彦鹏和景晓军对 FH-OFDMA通讯体系的简介。

08 最刺耳的音乐

现在让咱们回到文章最初最刺耳的音乐。我不知道陈奕迅是假如即兴创造出一首那么刺耳的音乐，但我猜想他的方针是打破观众的惯例等待─美丽的乐曲。那么什么是美丽的音乐呢？我想重复是一个要害。毕达哥拉斯早在 2500 年前就发现腔调之间的份额。一首乐曲有旋律，有主题。经过旋律和主题的重复。比方在贝多芬的第五交响曲中的闻名的“哒呐呐呐”四音符动机音型主题在交响乐中仅在榜首乐章里就有数百次。所以这种重复的设置关于美丽来说十分重要。那么，假如咱们能创造出一段没有任何重复的音乐，没有旋律，没有形式，没有份额。那么得到的便是一首十分刺耳的音乐。

这个思维其实早在 20 世纪 30-50 时代开端就有人尝试过。闻名的奥地利裔美国作曲家和音乐理论家阿诺德 勋伯格（Arnold Schoenberg，1874－1951）提出“解放不和谐”的思维，期望能从腔调结构中开释音乐。惋惜他在科斯塔斯处理了怎么在数学上发明这些结构的问题之前 10 年就逝世了。

经过了上面临科斯塔斯阵列的评论，咱们应该不难想到切入点便是科斯塔斯阵列。钢琴上有 88 个键，从最左面的低声 A（啦）到最右边的高音 C（哆）。咱们能够把科斯塔斯在声纳中的频率换成钢琴的琴键。正好p= 89 是一个素数。上面的评论让咱们知道能够结构一个 (p-1)×(p-1)= 88×88 的科斯塔斯阵列。又g= 3 是 GF(89) 的一个原根。所以咱们能够运用卫曲结构法来做。简略核算得到：

从这个核算，咱们得到下面的科斯塔斯阵列：

把它换成曲谱便是世界上首个无形式钢琴奏鸣曲（Costas Golomb No. 1: The Perfect Ping）：

在这个曲子中，88 个琴键的每一个都只演奏一次，并且是按上述科斯塔斯阵列的次序。

这段音乐是美国数学家、爱尔兰都柏林大学学院工学院高档讲师斯科特 里卡德（Scott Rickard）为咱们创造的。里卡德在麻省理工学院取得数学和核算机与工程学的两个本科学位（1992 年和 1993 年）和电子工程和核算机科学的硕士学位，又在普林斯顿大学取得运用数学和核算数学的硕士和博士学位（2000 年和 2003 年）。他在 2011 年的 TED 大会上介绍了这首乐曲。假如你能看到他的讲演视频，那么就能够赏识由新世界交响乐团室内音乐系主任迈克尔 林维（MichaelLinville）演奏的钢琴独奏。我不知道读者会怎样比较陈奕迅和林维的扮演，但咱们知道林维演奏的乐曲只需数学家能够创造出来。

本文经授权转载自微信大众号“和乐数学”，宣布在《我国工业与运用数学学会通讯》2019 年第 3 期。

特 别 提 示

1. 进入『返朴』微信大众号底部菜单“精品专栏“，可查阅不同主题系列科普文章。

2. 『返朴』供给按月检索文章功用。重视大众号，回复四位数组成的年份+月份，如“1903”，可获取2019年3月的文章索引，以此类推。

《返朴》，科学家领航的好科普。世界闻名物理学家文小刚与生物学家颜宁一同出任总编辑，与数十位不同范畴一流学者组成的编委会一同，与你一同求索。重视《返朴》（微信号：fanpu2019）参加更多评论。二次转载或协作请联络fanpusci@163.com。