PCM Map Generator

IRIG Standard 106 is the telemetry transmission standard used across aerospace, flight test and defense ranges. Chapter 4 defines the structure of the PCM stream itself.

A major frame is the fundamental repeating unit of the problem. It is the entire grid. It consists of \(M\) minor frames (rows), each carrying \(W\) words of \(w\) bits (columns). Three words in every minor frame are reserved overhead, leaving \(W - 3\) for measurement data.

The major frame rate \(f_{\mathrm{major}}\) is how many complete major frames go out per second. This is calculated with the bitrate, bits per word, words per minor frame, and minor frames per major frame.

Realisitcally, these are all buzzwords to non-instrumentation engineers. Just remember that a minor frame is a row, and every row is the same length. This means that each word per minor frame is a column.

Hard constraints

Every candidate grid is checked against Chapter 4 before it is allowed to compete. A candidate that violates any of these is marked invalid and excluded from selection entirely. These standards are universal across ranges, sites, and projects, so all hardware and software are built to adhere to them.

As you can see, pushing \(W\) up improves overhead efficiency (the case in which more data words exist per overhead words).

Three reserved words out of 1,024 costs almost nothing, out of 8 it costs 38% of the link. But \(w \cdot W\) runs into the 8,192-bit ceiling quickly, and a grid that is very wide and very short scores badly on balance. The optimum is somewhere in the middle, which is exactly why the tool searches instead of guessing.

Hopefully the clarity in the difficulty of this problem is more apparent now. However, this is still only one-half of the solution.

Measurements enter the grid through three commutation modes, and each imposes a different periodicity constraint. Periodicity is the concept of spacing a particular data word evenly throughout any repetition in a column or row.

Sub-commutation

When a measurement needs fewer than \(M\) samples per major frame, which in practice is almost always, it appears in a subset of minor frames at even row spacing:

If \(M\) is not divisible by the sample count the spacing cannot be even, and the stream physically cannot emit the data in that pattern, since, again, this grid simply is a representation of a 1-dimensional pulse-code-modulation stream (refer to animation). A measurement sampled 8 times in a 24-row grid appears in every third row: 0, 3, 6, 9, 12, 15, 18, 21.

Super-commutation

When a measurement needs more than \(M\) samples per major frame it has to appear several times within a minor frame, again evenly spaced, the same word repeated across the row at a fixed column pitch:

A measurement sampled 48 times in a 24-row grid appears twice per minor frame, at columns separated by \(W/2\).

In the third mode, the measurement appears exactly once per minor frame, in every row, with no column constraint at all. Time words behave this way, and rarely you will find a case where you want another word to do so as well. Sometimes, you want bus data or voice words to do this (though voice words tend to have a higher required sample rate).

The invariant is strict, and the wrap-around term is the part that is easy to miss: the gap from the last placement in a row back around to the first placement in the next row must equal the same period. Otherwise the sample interval stutters once per row.

The oversampling constraint

Analog measurements carry an anti-aliasing filter, and the filter imposes an oversampling factor on top of the rate the customer asked for. The algorithm applies it by multiplying the requested samples-per-second by an OVERSAMPLING_FACTOR the engineer supplies.

Digital sources bypass this because their stated rate is their actual rate. An analog vibration channel can end up demanding an order of magnitude more grid capacity than the requirement from the customer may suggest, while a digitised voice channel demands exactly what it says and no more.

The optimal words_per_minor depends on how many samples each super-commutated group needs per minor frame. But that per-minor sample count depends on words_per_minor, because samples_per_minor must divide words_per_minor evenly for the column spacing to be periodic.

Well... that poses a problem, since neither can be chosen first. My resolution is a two-pass allocation.

Pass 1: Size the grid and ignore the columns

The first pass deliberately drops the column-divisibility constraint so a width can be chosen at all. _choose_actual_samples_per_major() is called without words_per_minor, so it returns the minimum valid sample count: the smallest value at or above the requirement that divides minor_frames, or is a multiple of it.

*note, the following blocks of code are NOT the actual code, but rather just examples so you can see what an implementation may look like.

for group in groups:
    factor = get_sampling_factor(getattr(group, 'input_type', 'frequency_interest'))
    effective_minimum = group.minimum_sps_each * factor
    needed = ceil(effective_minimum / reqs.major_frame_rate)

    actual = _choose_actual_samples_per_major(needed, minor_frames)
    # ↑ Pass 1: no words_per_minor argument — column-divisibility unconstrained

    pass1_actuals.append(actual)
    er_count = getattr(group, 'extended_read_count', 0)
    total_data_words_p1 += group.count * actual * (1 + er_count)

def _choose_actual_samples_per_major(needed, minor_frames, words_per_minor=None):
    if needed <= 0:
        return 1

    if needed <= minor_frames:
        # Sub-comm: find smallest count >= needed that divides minor_frames
        for candidate in range(needed, minor_frames + 1):
            if minor_frames % candidate == 0:
                return candidate
        return minor_frames  # worst case: once per minor frame

    # Super-comm: ceil(needed / minor_frames) samples per minor frame
    spm = ceil(needed / minor_frames)

    # If words_per_minor is known, round spm up to nearest divisor of W
    if words_per_minor is not None and spm > 1 and words_per_minor % spm != 0:
        for candidate_spm in range(spm + 1, words_per_minor + 1):
            if words_per_minor % candidate_spm == 0:
                spm = candidate_spm
                break
        else:
            spm = words_per_minor  # worst case: entire row

    return spm * minor_frames

Pass 2: Re-allocate with column divisibility active

With a width in hand, every group is re-allocated, this time passing words_per_minor through. Rounding samples_per_major up to the nearest divisor of \(W\) can only increase the sample count, which can only increase total data words — so Pass 2 can retroactively invalidate the width Pass 1 chose.

for group in groups:
    actual = _choose_actual_samples_per_major(
        needed,
        minor_frames,
        words_per_minor,   # ← column-divisibility active
    )

data_per_minor_needed = ceil(total_data_words / minor_frames)

if data_per_minor_needed + overhead_per_minor > words_per_minor:
    # Pass-2 rounding blew past chosen width — bump to next preferred size
    words_per_minor = _choose_preferred_words(
        data_per_minor_needed + overhead_per_minor,
    )
    if words_per_minor is None:
        return None  # Exceeds IRIG limit

The scoring function

Dimensioning admits many valid solutions, so candidates are ranked by a weighted composite score. The weights encode what a good grid actually means to an instrumentation engineer, not what is mathematically tidy.

\(d(n)\) is the divisor count — \(d(24) = 8\), since 24 is divisible by 1, 2, 3, 4, 6, 8, 12 and 24. A highly divisible \(M\) gives the placement phase far more legal row periods to work with, which is why it earns its own term.

The multiplier score uses the asymptote \(1 - 1/\alpha\) deliberately. At \(\alpha = 1\) it scores 0, with corresponds to no oversampling at all. At \(\alpha = 2\) it scores 0.5. It approaches 1.0 but never reaches it, so the function rewards oversampling while giving sharply diminishing returns for extremity. That is the desired behaviour: 4× oversampling is much better than 1×, and 40× is barely better than 4× while costing ten times the bandwidth.

The weights sum to 0.90, not 1.00, and that 10% gap is load-bearing. A single spacing violation costs 0.5 — more than the entire balance and divisibility terms combined. No amount of elegance elsewhere can rescue a candidate that cannot place its groups periodically, which is exactly the ordering an engineer would want.

score = (
    0.35 * multiplier_score
    + 0.20 * spare_score
    + 0.10 * divisor_score
    + 0.10 * overhead_efficiency
    + 0.15 * balance_score
    - spacing_penalty
)
return round(score, 6)

The round(score, 6) is put in place to get rid of comparison errors due to floating-point inprecision. Candidates are later sorted by score, and two functionally identical scores that differ in the last floating-point bit can sort differently across Python versions. This tool ships to offline laptops that cannot easily be upgraded, so a version-dependent tie-break would surface as two engineers on two machines getting two different maps from identical inputs.

dang hardware constraints!

Candidate enumeration

The search is brute force with a deliberate expansion step.

def _enumerate_candidates(groups, target_bit_rate, bits_per_word,
                         overhead_per_minor, time_words_per_minor):
    reqs = compute_aggregate_requirements(groups)
    candidates = []

    for minor_frames in CANDIDATE_MINOR_FRAMES:      # 20 values
        # Build minimum-width baseline
        baseline = _build_candidate(groups, reqs, minor_frames, ...)
        if baseline is None:
            continue
        baseline.score = _score_candidate(baseline, target_bit_rate)
        candidates.append(baseline)

        # Explore 3 wider configurations (for grid balance)
        wider_sizes = _choose_preferred_words_multi(
            baseline.words_per_minor + 1, max_extras=3
        )
        for wpm in wider_sizes:
            candidate = _build_candidate(..., words_per_minor_override=wpm)
            if candidate is not None:
                candidate.score = _score_candidate(candidate, target_bit_rate)
                candidates.append(candidate)

    return candidates

The space is at most 20 minor-frame counts × (1 baseline + 3 wider) = 80 candidates, each built in \(O(G)\). Ultimately, a very reasonable time complexity.

One button — “Generate PCM map and export” — fans out into seven stages. Validation happens early, the expensive CSP happens last, and every stage has a single well-defined output.

Stage 3 runs the entire candidate enumeration once at the 10 Mbps ceiling purely to discover the minimum feasible bit rate, then adds the operator’s spare margin to set the real target. It is a full extra pass over the search space, which is spent to convert “pick a bit rate then hope and pray" into “here is the floor, here is your margin, here is the request you take to the range.”

Backtracking is a depth-first search over partial assignments: build a solution one measurement at a time, and when a later choice hits a dead end, undo the most recent choice and try the next option instead.

Step 1: sample decomposition

decompose_samples() turns a total sample count into a placement shape (rows_used, samples_per_minor, row_period) satisfying three properties: never undersample, even row spacing, and even column spacing. Three fast paths handle the common cases before an exhaustive search is needed.

def decompose_samples(actual_samples, rows, cols):
    # Fast path 1: pure sub-comm
    if actual_samples <= rows and rows % actual_samples == 0:
        return actual_samples, 1, rows // actual_samples

    # Fast path 2: pure super-comm (spm divides cols)
    if actual_samples >= rows and actual_samples % rows == 0:
        spm = actual_samples // rows
        if spm == 1 or (cols % spm == 0 and cols // spm >= 1):
            return rows, spm, 1

    # Exact decomposition search
    for rows_used in range(min(actual_samples, rows), 0, -1):
        if rows % rows_used != 0:
            continue
        if actual_samples % rows_used != 0:
            continue
        spm = actual_samples // rows_used
        if spm > 1 and cols % spm != 0:
            continue
        return rows_used, spm, rows // rows_used

    # Round-up fallback: smallest spm divisor of cols >= ceil(actual/rows)
    min_spm = (actual_samples + rows - 1) // rows
    for spm in _col_divisors(cols):
        if spm < min_spm:
            continue
        if cols // spm < 1:
            continue
        return rows, spm, 1

    raise ValueError(f"Cannot decompose {actual_samples} ...")

This solution finds the smallest samples-per-minor that both divides the column count and meets the minimum. It raises the oversampling factor above what was asked for every time, but it guarantees periodic placement. This effectively happens at least once to every measurement. Before I figured this out, I would generate nothing but broken maps.

Step 2: Grouping extended-read words

A bus word wider than \(w\) bits is emitted as a parent plus companions. They are identified by regex and fused into a single indivisible placement unit before the solver ever sees them.

_ER_PATTERN = re.compile(r"^(.+?)_ER(\d*)$")

for m in measurements:
    match = _ER_PATTERN.match(m.name)
    if match:
        parent = match.group(1)
        if parent in by_name:
            er_groups.setdefault(parent, []).append(m.name)

# Sort: _ER before _ER1 before _ER2 (by length then lexicographic)
for parent, companions in er_groups.items():
    companions.sort(key=lambda n: (len(n), n))

A parent M1 with companions M1_ER and M1_ER2 becomes one PlacementSpec of width 3 with labels = [M1, M1_ER, M1_ER2]. During placement the block occupies three consecutive columns and cannot be split, which makes it one of the most constrained things in the grid.

Still, its a necessity, since you cannot place an extended-read on a 12bit/word system thats 36 bits after the initial read. You'd be concatenating random bits to the end of your measurement.

Step 3: backtracking with forward checking

def _backtrack(specs, index, grid, placements, deadline):
    if index == len(specs):
        return True                       # All placed

    if time.time() > deadline:
        return False                      # Timeout → greedy fallback

    spec = specs[index]
    candidates = _enumerate_offsets(spec, grid)

    for row_off, col_off in candidates:
        cells = generate_cells(spec, row_off, col_off, ...)
        if cells is None:
            continue
        if not all(grid.is_free(r, c) for r, c, _ in cells):
            continue

        # Place all cells
        for r, c, label in cells:
            grid.place(r, c, label)
        placements[index] = cells

        # Forward check: verify all remaining specs have >= 1 valid offset
        if index + 1 < len(specs):
            if not _forward_check(specs[index + 1:], grid):
                for r, c, _ in cells:     # Undo and try next candidate
                    grid.unplace(r, c)
                placements[index] = []
                continue

        if _backtrack(specs, index + 1, grid, placements, deadline):
            return True

        # Undo
        for r, c, _ in cells:
            grid.unplace(r, c)
        placements[index] = []

    return False

When the solver backtracks from level \(k\) to level \(k-1\) it must restore the grid to exactly the state it was in before the level \(k-1\) choice. That is why PeriodicGrid exposes both place() and unplace(). Together they form a reversible state machine, and, naturally, you'd want an exact reversal with the sort of constraints that come with PCM telemetry.

A greedy placer takes each measurement’s first valid offset and never looks back. That fails as soon as measurements compete for the same cells: accelerometer A1 wants columns 1 and 25 in every row, A2 wants the same columns at the same rate, and once A1 has them A2 is stuck shuffling into whatever is left, which is possibly nothing. Backtracking can undo A1 and move it to column 2, freeing column 1 for A2.

So, practically, the ability to reconsider makes the search complete because it finds a valid arrangement whenever one exists.

Three enhancements over naive backtracking

The implementation adds three things that turn a theoretically exponential algorithm into a practical one.

Every failure mode has a named detection point and a defined recovery. Two of them are recoveries; the rest are deliberate refusals to produce a wrong map.

Performance

Complexity is bounded everywhere except the solver, and the solver is bounded by wall clock rather than by proof.

Where performance actually matters

Exactly one place: the inner loop of the backtracker.

for row_off, col_off in candidates:
    cells = generate_cells(...)                          # ← allocation-heavy
    if cells is None:
        continue
    if not all(grid.is_free(r, c) for r, c, _ in cells):  # ← O(cells) checks
        continue

    for r, c, label in cells:
        grid.place(r, c, label)                          # ← 2 array writes

    # ... forward check ...

    for r, c, _ in cells:
        grid.unplace(r, c)                               # ← 2 array writes

generate_cells() allocates a fresh list of tuples on every call. For a super-commutated measurement on a 24×48 grid with spm=2 that is 48 (int, int, str) tuples per call, and a tight loop trying dozens of offsets generates thousands of short-lived allocations that pressure CPython’s small-object allocator.

While this fix is known, I didn't have time to implement. Since this is being run completely locally on one machine at a time, though, it doesn't really matter... and I'm really just nitpicking for specifics right now.