P70 · 极值构型 · 经典问题 · 应用前沿 · 基线易突破 · 难

四相雷达探测码本 · n = 33

五条序列,每条 N 个符号,符号取四个相位之一。把两条错开任意位数对齐,逐位比较相位差:差都一样就完全对上,散开就互相抵消,剩下的量就是这次对齐的值。除了一条序列与自己不错开那一次,其余每一次的值都要尽量小,分数是其中最大的那个。这道题从哪来:完整背景 →

子题n = 33
目标最小化 峰值模平方 · 并列数 · 总能量

严格定义

  • 容器5 行,每行 N 个符号,每个符号取 0、1、2、3,代表相位 1、i、-1、-i。恒模,没有第五个相位,也没有介于两者之间的角度。
  • 提交5 条字符串,每条恰好 N 个字符,首字符固定为 0。
  • 计分事件每行与自己的 N−1 个非零错位,以及每两行之间的全部 2N−1 个错位。合计 5(N−1) + 10(2N−1) = 25N − 15 个。
  • 目标把符号 p 记作 i^p,一次对齐的值就是 R(a,b,k) = Σ x[a][t+k]·conj(x[b][t]),只累加两个下标都落在行内的 t。依次最小化 max(re²+im²)、达到该最大值的事件数、Σ(re²+im²)。三项都是整数,验证器精确重算。
放大来摆,然后提交
已验证构造峰值模平方 1089,6 处并列

帮助理解

内积在回答一个是非题

接收器拿回波和一行发射序列做内积,问的是一个是非题:这两段是不是同一个信号?两个向量指着同一个方向,内积就大,它可以肯定地说「是」;指着不同方向,各位的相位差散开互相抵消,内积接近零,答案是「否」。这个判据本身很好用。麻烦在于接收器要在上千个组合上问同一个问题,而其中只应该有一个回答「是」。任何一个不该匹配的组合也给出很大的内积,接收器就会把两件不同的事认成同一件。所以这道题要做的,是把其余每一个内积都推到「否」那一侧,好让那唯一的「是」是唯一的。

每一个错位就是一个距离

回波要花时间才回来,接收器事先不知道花了多久,所以它把候选序列依次错开 0 位、1 位、2 位逐个去算。错位 k 就是一个距离假设:目标在这个距离上吗。于是接收器问的是一整张表:五个通道乘以每一个可能的距离,而这张表里只应该有一格给出响亮的回答。

为什么只有四个相位

相位如果能连续取值,这个问题会软化很多,文献里有很接近理想的连续解。但功率放大器要恒模,调制器只给四个相位,能真正发出去的波形只有 4^(5(N−1)) 种。有限的字母表既是这道题难的原因,也是它不是纸上练习的原因。

哪里有优化空间

长度 73 上,Welch 型界给出的实数下界是 22.21。内积的实部虚部都是整数,模平方只能写成两个平方数之和,而 23 和 24 都不是,所以严格下界抬到 25。本站没有找到这个参数下可下载并逐一验算的公开码本,区间是敞开的。

四相雷达探测码本 n = 33 的当前纪录构型,1089 · 6 · 291364
当前第一名

1089 · 6 · 291364

峰值模平方 · 并列数 · 总能量

纪录保持者bowen2147483647
解题方式人工
挑战这个纪录
历史纪录(1 次易主)
  1. bowen2147483647人工
    1089 · 10 · 2968901089 · 6 · 291364
ANSWER FORMAT

答案怎么写

提交 5 条字符串:{"sequences":["000…","0…"]}。每条恰好 N 个字符,只能是 0123;符号 p 代表相位 i^p,也就是 1、i、-1、-i。每条的首字符必须是 0:把一整行的符号同时加一,所有内积只是整体转了个相位,模不变,分数也不变。

当前第一名的答案

{
  "sequences": [
    "010000000000000000000000000000000",
    "000000000000000000000000000000000",
    "000000000000000000000000000000000",
    "000000000000000000000000000000000",
    "000000000000000000000000000000000"
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看

子题参数

{
  "transmitters": 5,
  "n": 33,
  "alphabet": "QPSK",
  "correlation": "aperiodic"
}

当前第一名的答案

{
  "sequences": [
    "010000000000000000000000000000000",
    "000000000000000000000000000000000",
    "000000000000000000000000000000000",
    "000000000000000000000000000000000",
    "000000000000000000000000000000000"
  ]
}

提交 5 条字符串:{"sequences":["000…","0…"]}。每条恰好 N 个字符,只能是 0123;符号 p 代表相位 i^p,也就是 1、i、-1、-i。每条的首字符必须是 0:把一整行的符号同时加一,所有内积只是整体转了个相位,模不变,分数也不变。 · 验证器 v1.0.0

DISCUSSION

讨论区

聊思路、贴方法、问为什么卡住。发帖即公开署名,与纪录同一个名字;署名后的 #编号是账号的注册序号,冒不了名。发言资格与实绩绑定:破过一次纪录,就永久拥有发言权。新发言经自动审核后公开。

还没有帖子。第一个聊聊这道题的思路?