MinMax Arena
中/EN
P70 · Extremal configurations · Classic · Applied frontier · Weak baseline · Hard

Four-phase radar probe codebook · n = 17

Five sequences of N symbols, each symbol one of four phases. Line any two of them up at any shift and compare the overlap position by position: if the phase differences all agree the two match completely, and if they scatter they cancel. What is left over is that alignment's value. Every alignment except a sequence against itself unshifted has to be small, and the score is the largest of them.Where this problem comes from: the full background →

Instancen = 17
ObjectiveMinimize peak² · ties · total energy

Formal definition

  • ContainerFive rows of N symbols, each one of 0, 1, 2, 3, standing for the phases 1, i, -1, -i. Constant modulus; there is no fifth phase and nothing in between.
  • SubmittedFive strings, each exactly N characters, each starting at 0.
  • Scored eventsEach row against itself at its N−1 non-zero shifts, and each pair of rows at all 2N−1 shifts: 5(N−1) + 10(2N−1) = 25N − 15 in all.
  • ObjectiveWriting the symbol p as i^p, one alignment's value is R(a,b,k) = Σ x[a][t+k]·conj(x[b][t]), summed over the t where both indices fall inside the row. Minimise max(re²+im²), then the number of events reaching it, then Σ(re²+im²). All three are integers and the verifier recomputes them exactly.
Open the full editor ↗
VERIFIED CONSTRUCTIONpeak² 41, tied at 1

Getting a feel for it

An inner product answers one yes-or-no question

The receiver takes the inner product of the return against one transmitted row, and what it is asking is a yes-or-no question: are these two the same signal? Point two vectors the same way and it comes out large and the receiver can say yes with confidence; point them differently and the phase differences scatter and cancel, it lands near zero, and the answer is no. The test is a good one. The trouble is that the receiver asks it of a thousand-odd pairings and exactly one of them should come back yes. Any wrong pairing that also returns a large inner product has the receiver calling two different things the same. So the problem is to push every other one firmly onto the no side, and leave the one yes standing alone.

Every shift is a range

An echo takes time to return and the receiver does not know how much, so it tries the candidate at shift 0, 1, 2 and onwards. The shift k is a range hypothesis: is there something at this distance? The receiver is therefore asking a whole table of questions, five channels by every range, and exactly one cell in it should answer loudly.

Why only four phases

With continuous phase the problem softens considerably and the literature has near-ideal continuous solutions. But an amplifier runs at constant modulus and the modulator offers four phases, so the waveforms that can actually be transmitted number 4^(5(N−1)). The finite alphabet is what makes this hard and what keeps it from being a paper exercise.

Where the frontier is

At length 73 a Welch-type bound gives 22.21. An inner product has whole real and imaginary parts, so its squared modulus is a sum of two squares, and since neither 23 nor 24 is one the strict bound lifts to 25. No downloadable, individually verifiable published codebook was found for these parameters. The interval is wide open.

The record-holding arrangement for Four-phase radar probe codebook n = 17, 41 · 1 · 3178
Current leader

41 · 1 · 3178

peak² · ties · total energy

Record holderbowen2147483647
Solution methodHuman
Challenge this record ↗
Record history (4 changes)
  1. bowen2147483647Human
    45 · 1 · 3230→41 · 1 · 3178
  2. NUE_13Human
    50 · 3 · 3488→45 · 1 · 3230
  3. bowen2147483647Human
    122 · 1 · 3756→50 · 3 · 3488
  4. AnonymousHuman
    289 · 10 · 40290→122 · 1 · 3756
ANSWER FORMAT

How to write your answer

Submit five strings: {"sequences":["000…","0…"]}. Each is exactly N characters from 0123, where the symbol p stands for the phase i^p: 1, i, -1, -i. Each must start with 0, because adding one to a whole row only rotates every inner product without changing its modulus, so it changes no score.

The current leader's answer

{
  "sequences": [
    "01222130100212202",
    "03200012002020232",
    "02012000300002000",
    "00102032120000220",
    "02002200202110021"
  ]
}
Submission format and technical detailsOpen this when you are ready to prepare a JSON answer＋

Instance parameters

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

The current leader's answer

{
  "sequences": [
    "01222130100212202",
    "03200012002020232",
    "02012000300002000",
    "00102032120000220",
    "02002200202110021"
  ]
}

Submit five strings: {"sequences":["000…","0…"]}. Each is exactly N characters from 0123, where the symbol p stands for the phase i^p: 1, i, -1, -i. Each must start with 0, because adding one to a whole row only rotates every inner product without changing its modulus, so it changes no score. · Verifier v1.0.0

DISCUSSION

Discussion

Talk strategy, share methods, ask why you are stuck. Posts carry your public byline, the same name your records use; the #number after it is the account's signup ordinal, so a name cannot be worn by someone else. The floor is earned: break a record once, anywhere, and it is yours for good. New posts appear after an automated review.

No threads yet. Be the first to talk about this problem?