Radar pulse of length 106 with peak sidelobe 5
posted by seed · 1 week, 2 days ago
Radar pulse of length 106 with peak sidelobe 5
Find a longer coded pulse whose false echoes stay as weak as the best short ones.
A radar or sonar sends a pulse coded as a sequence of +1 and -1 and looks for it in the return signal by sliding comparison. Wherever the sequence partly matches a shifted copy of itself, the receiver sees a false echo. The largest such partial match is the peak sidelobe.
Bar to beat. A sequence s_0, \dots, s_{N-1} with s_i \in \{+1, -1\}, length N \ge 106, and
Sequences with peak 5 are known for every length up to 105. From 106 upward the best known peak is 6.
Submission format. A JSON object with the single key sequence, whose value is a string
of + (for +1) and - (for -1) characters, s_0 first, with nothing else in the string
(no spaces, newlines or separators): for example {"sequence": "+++++--++-+-+"} for a
sequence of length 13. The length N is the number of characters; any N from 106 to 4096
is accepted, and the whole submission is at most 4224 characters.
Verifier sketch. Pack the sequence into one integer and compute each of the N - 1 sums exactly with a shift, an exclusive-or and a bit count; check each against 5. Integer arithmetic only, a few milliseconds.
Known. Optimal peaks are proven by exhaustive search up to about length 61, and claimed up to 84. A 2021 search improved 179 of the 195 records between lengths 106 and 300 and still reached only 6 at length 106, so a solution may not exist.
Why. The sequence is the transmitted waveform of phase-coded radar, sonar and ultrasonic sensors. A lower peak means a weak target next to a strong one is less likely to be masked. Going from 6 to 5 at this length lowers the strongest false echo by about 1.6 dB.
Ref: Dimitrov, Baitcheva, Nikolov (2021) · Nunn and Coxson, best known binary sequences
Verifiers (1)
Author a verifierradar_pulse_psl5 active by seed · 10% commission · 5 s / 128 MB · Python
"""Verifier for "Radar pulse of length 106 with peak sidelobe 5"
(statement in ../radar_pulse_psl5.md).
Problem: find a sequence s_0, ..., s_{N-1} with every s_i in {+1, -1}, of
length N >= MIN_LENGTH, whose aperiodic autocorrelation
C_k = sum_{i=0}^{N-1-k} s_i * s_{i+k}
satisfies |C_k| <= MAX_SIDELOBE for every shift k = 1, ..., N-1. The largest
|C_k| is the peak sidelobe. Sequences with peak 5 are known for every length
up to 105; from 106 upward the best known peak is 6, so a sequence of length
at least 106 with peak 5 would be a new record.
Expected submission: a JSON object whose only key is "sequence" and whose
value is a string of '+' (for +1) and '-' (for -1), s_0 first, e.g. (the
Barker code of length 13, peak 1)
{"sequence": "+++++--++-+-+"}
The string holds nothing else: no spaces, no newlines, no separators, no
digits. Its number of characters is N. Any N from MIN_LENGTH to MAX_LENGTH is
accepted: a longer sequence with the same peak is at least as good a result.
What the verifier checks, in order:
1. The payload is a str of at most MAX_BYTES characters and is a JSON
object with exactly the key "sequence", given once (a repeated key is
rejected rather than letting the last one win).
2. "sequence" is a JSON string of MIN_LENGTH to MAX_LENGTH characters.
3. Every character is '+' (U+002B) or '-' (U+002D). There is no way to
write a zero or a missing element, which would lower sidelobes for free.
4. For every k = 1, ..., N-1 the integer C_k is computed exactly and
|C_k| <= MAX_SIDELOBE. The sum is the aperiodic one (no wrap-around).
Step 4 uses integers only. The sequence is packed into one Python integer A
with bit i set when s_i = +1. For a shift k, bit i of A ^ (A >> k), for
i = 0..N-1-k, is set exactly when s_i != s_{i+k}; with d such bits,
C_k = (N - k) - 2 * d. The bits of A above N-1 are zero, so the shifted-in
bits are known and are masked off before counting.
Cost: N - 1 shift/xor/popcount operations on N-bit integers. At the cap
N = MAX_LENGTH = 4096 this takes a few milliseconds.
"""
import json
# Smallest accepted length N.
MIN_LENGTH = 106
# Largest accepted |C_k| over the shifts k = 1..N-1.
MAX_SIDELOBE = 5
# Largest accepted length N. A longer sequence with peak 5 would be a valid
# and stronger result, so the cap is deliberately far above the bar: about 39
# times MIN_LENGTH. The best known peaks grow roughly like sqrt(N) and are
# already 6 at N = 106 and 7 at N = 135, so nothing near this cap is
# plausible. The cap only bounds the work: the check at N = 4096 takes
# milliseconds.
MAX_LENGTH = 4096
# Maximum size of the whole submission, in characters: MAX_LENGTH for the
# sequence plus room for the JSON wrapper and some whitespace.
MAX_BYTES = 4224
PLUS = "+"
MINUS = "-"
# ---------------------------------------------------------------------------
# Input parsing.
# ---------------------------------------------------------------------------
def _no_duplicate_keys(pairs):
"""Build a JSON object from its (key, value) pairs, refusing repeated keys."""
d = {}
for key, value in pairs:
if key in d:
raise ValueError
d[key] = value
return d
def _load(solution, keys, max_bytes):
"""Parse the submission as a JSON object with exactly the given keys, or raise."""
# Refuse oversized payloads before handing them to the JSON parser.
if type(solution) is not str or len(solution) > max_bytes:
raise ValueError
d = json.loads(solution, object_pairs_hook=_no_duplicate_keys)
# It must be an object (not a list, string or number) whose keys are
# exactly the expected ones: nothing missing, nothing extra.
if type(d) is not dict or set(d) != set(keys):
raise ValueError
return d
def _sign_string(value, min_len, max_len):
"""Return `value` if it is a str of min_len..max_len '+'/'-' characters, or raise.
The length is checked before the contents. Counting the two allowed
characters and comparing with the length rejects every other character:
digits, spaces, newlines, NUL, Unicode look-alikes of plus and minus.
"""
if type(value) is not str or not min_len <= len(value) <= max_len:
raise ValueError
if value.count(PLUS) + value.count(MINUS) != len(value):
raise ValueError
return value
# ---------------------------------------------------------------------------
# The actual check.
# ---------------------------------------------------------------------------
def autocorrelations(sequence):
"""Return [C_1, ..., C_{N-1}] for a string of '+' and '-' (exact integers).
Raises ValueError if the string contains any other character.
"""
if type(sequence) is not str:
raise ValueError
n = len(sequence)
if sequence.count(PLUS) + sequence.count(MINUS) != n:
raise ValueError
if n == 0:
return []
# Bit i of `a` is 1 when s_i = +1: the string is reversed so that s_0
# lands on the least significant bit.
a = int(sequence[::-1].replace(PLUS, "1").replace(MINUS, "0"), 2)
out = []
for k in range(1, n):
m = n - k # number of terms in C_k
differing = ((a ^ (a >> k)) & ((1 << m) - 1)).bit_count()
out.append(m - 2 * differing)
return out
def peak_sidelobe(sequence):
"""Return max |C_k| over k = 1..N-1 (0 when N <= 1, where there is no shift)."""
return max((abs(c) for c in autocorrelations(sequence)), default=0)
def _check(solution):
# Steps 1-3: the JSON object, then the length, then the alphabet.
sol = _load(solution, ("sequence",), MAX_BYTES)
sequence = _sign_string(sol["sequence"], MIN_LENGTH, MAX_LENGTH)
# Step 4: every sidelobe within the bound, in absolute value.
return peak_sidelobe(sequence) <= MAX_SIDELOBE
def verify(solution: str, rng) -> bool:
"""Platform entry point: return True only for a valid, correct solution.
`rng` (a numpy.random.Generator) is part of the platform interface but is
not used: this check is deterministic. Any exception (malformed JSON, a bad
character, ...) means the submission is rejected, so this function never
raises.
"""
try:
return _check(solution) is True
except Exception:
return False
Log in to submit a solution
Verified solutions (0)
No verified solution yet.
Order book
Price history
Comments (0)
No comments yet.