PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved bounds for constant-power and low-power error-correcting cooling codes

Tingting Tong, Sihuang Hu

arXiv:2609.35061v1cs.ITmath.COmath.IT

TL;DR

Controlling total switching does not prevent a few bus wires from repeatedly switching and becoming hotter, while existing bounds for e = w−3 had restrictive weight conditions. This paper uses 3-shadow bounds and constructions for binary CPECC and LPECC codes. It reduces the thresholds to order t^3/2, strengthens the LPECC bound, and establishes asymptotic tightness in the stated ranges.

  • Problem

    Existing e = w−3 bounds had restrictive weight conditions, and strengthening the LPECC bound requires separate treatment because information classes can contain transition vectors of different weights.

    Source: §1 · p. 3

  • Method

    The proofs use uniform and mixed-weight 3-shadow bounds, with lifting and compression for the mixed-weight LPECC case.

    Source: §1 · p. 4, §5 · p. 22

  • Results

    Both weight thresholds are reduced to order t^3/2; the new LPECC bound is strictly stronger whenever it and Zhao and Zhang’s bound both apply, and is asymptotically tight in the stated range.

    Source: §1 · p. 4, §5 · p. 22

  • Takeaways & Limitations

    For fixed t and w in the respective parameter ranges, the paper determines the asymptotic sizes of both CPECC and LPECC codes.

    Source: §5 · p. 22

    Exact Steiner-system attainment depends on such systems existing, which holds for sufficiently large admissible lengths.

    Source: §3.2 · p. 13

Abstract

from arXiv · show

Low-power error-correcting cooling (LPECC) codes and constant-power error-correcting cooling (CPECC) codes provide error correction while controlling power consumption and thermal effects in on-chip buses. In this paper, we study binary CPECC and LPECC codes with \(e=w-3\). For CPECC codes, we extend the applicability of the upper bound previously obtained by Zhao and Zhang from the quadratic-order condition \(w\ge 2t(t+1)+2\) to \(w\ge w_0(t)\), where \(w_0(t)\sim \sqrt{2}\,t^{3/2}\). Using Steiner systems, we show that the CPECC bound is attainable and asymptotically tight for fixed \(t,w\). For LPECC codes, we establish the new upper bound \(\left\lfloor\frac{\binom{n+2}{3}}{\binom{w+t}{3}}\right\rfloor\) for \(w\ge \mu(t)\), where \(\mu(t)\sim \sqrt{2}\,t^{3/2}\). This bound is strictly smaller than the previous bound of Zhao and Zhang whenever both apply, and is asymptotically tight for fixed \(t,w\) in the stated range.

1 Introduction

Cooling codes address the mismatch between limiting total bus switching and preventing repeated switching on a few wires. For e = w−3, the paper extends CPECC bounds to a weaker weight condition and strengthens the LPECC bound, with both thresholds reduced to order t^3/2.

  • Cooling codes let an encoder avoid transitions on the hottest wires; LPECC codes additionally limit total transitions and correct up to e transmission errors.CPECC instead requires exactly w transitions per transmission.Source: §1 · pp. 1–2
  • For CPECC codes, the Zhao–Zhang upper bound remains valid under w ≥ w0(t), and Steiner systems attain it exactly while asymptotically optimal 3-packings attain it asymptotically.The resulting construction is asymptotically tight for fixed t and w in the stated range.Source: §1 · p. 3
  • For LPECC codes with t ≥ 1, w ≥ µ(t), and n ≥ w+t, the paper establishes a stronger upper bound that is asymptotically tight.The CPECC constructions also qualify as LPECC codes, yielding the asymptotic tightness result.Source: §1 · pp. 3–4
  • Both CPECC and LPECC weight thresholds fall from quadratic order to order t^3/2, while the LPECC result also improves the finite-length upper bound.The CPECC result extends the range for proving optimality; the LPECC bound is strictly smaller than Zhao and Zhang’s whenever both apply.Source: §1 · pp. 3–4
  • The proofs use disjoint 3-shadows of information classes: a uniform 3-shadow bound handles CPECC, while lifting and compression address mixed-weight LPECC families.For LPECC, smaller-weight vectors receive separate treatment.Source: §1 · p. 4

2 Preliminaries

The preliminaries represent codes as information classes of subsets and relate their distance and transversal properties to set-family shadows. They also introduce packings and Steiner systems used in later constructions.

2 Preliminaries

  • A binary vector is identified with its support, whose size is its Hamming weight; the Hamming distance between supports A and B is |A△B|.Source: §2 · p. 4
  • An (n,t,w,e)-LPECC code consists of pairwise disjoint nonempty information classes satisfying cross-class distance at least 2e+1; CPECC blocks all have size w.The code size is the number of information classes.Source: §2 · pp. 4–5
  • Property A(t) means no t-subset is a transversal, while the 3-shadow collects triples contained in blocks; distinct information classes have disjoint 3-shadows when e=w−3.A transversal meets every member of a family.Source: §2 · pp. 4–5
  • An r-(v,k,1) packing covers each r-subset at most once, while a Steiner system covers each r-subset exactly once.For r=3, packing blocks intersect in at most two points.Source: §2 · pp. 5–6

3 Uniform 3-shadow bounds and CPECC codes

For e=w−3, the paper extends the CPECC upper bound to a lower weight threshold and establishes the uniform 3-shadow estimate behind it. Steiner systems and asymptotically optimal 3-packings provide matching constructions.

3.1 The uniform 3-shadow bound

  • The uniform 3-shadow theorem bounds the triple-shadow size of w-uniform families with transversal number at least t+1, enabling code bounds because distinct classes have disjoint 3-shadows.The thresholds w0(1)=5 and w0(2)=7 are best possible.Source: §3 · p. 6, §3.1 · pp. 11–12, §3.2 · p. 12

3.2 Bounds and constructions for CPECC codes

  • Steiner systems attain the CPECC upper bound exactly, and asymptotically optimal 3-packings yield asymptotically attaining constructions for fixed t and w.The Steiner-system construction applies when an S(3,w+t,n) exists.Source: §3.2 · pp. 12–14
  • The CPECC upper bound applies for w≥w0(t), reducing the sufficient weight requirement from quadratic order to order t^3/2.The earlier condition is w≥2t^2+2t+2.Source: §3 · p. 6, §3.2 · p. 13

4 Nonuniform 3-shadow bounds and LPECC codes

The paper derives a stronger LPECC upper bound from a mixed-weight 3-shadow estimate, improving on Zhao and Zhang’s bound whenever both apply. Its argument handles normal information classes and the possible exceptional class separately.

4 Nonuniform 3-shadow bounds and LPECC codes

  • At most one information class can be exceptional; all others are normal, with block sizes in {w, w−1, w−2}.The proof combines a shadow bound for normal classes with a separate contribution from the possible exceptional class.Source: §4 · p. 14, §4.2 · p. 20

4.1 The nonuniform 3-shadow bound

  • Lifting alone may not preserve transversal number, so compression makes family members contain the same two points without increasing 3-shadow size.After compression and deletion of those points, the resulting family retains at least the original transversal number.Source: §4.1 · pp. 15–16
  • The mixed-weight 3-shadow bound applies when w ≥ μ(t) and supplies the shadow estimate used to derive the LPECC upper bound.The proof reduces the bound to families formed by adjoining a fixed two-point set to a family with sufficiently large transversal number.Source: §4.1 · p. 18

4.2 Upper Bounds for LPECC Codes

  • For LPECC codes, the proof lifts normal classes using the same two new points and accounts separately for the possible exceptional class.The lifted 3-shadows of distinct normal classes are disjoint.Source: §4.2 · pp. 20–21
  • The LPECC upper bound is strictly smaller than Zhao and Zhang’s whenever both bounds apply, and its sufficient weight condition is weaker.The paper derives the bound for w ≥ μ(t).Source: §4 · p. 14, §4.2 · p. 21

5 Conclusion

For binary CPECC and LPECC codes with e = w−3, the paper reduces the required weight scale from quadratic order to order t^3/2. It extends the CPECC bound’s range and gives a stronger LPECC bound that is asymptotically tight in the stated range.

5 Conclusion

  • The CPECC upper bound applies under the weaker condition w ≥ w0(t), and is attained when an S(3,w+t,n) exists.The conclusion also states that it is asymptotically tight for fixed t and w.Source: §5 · p. 22
  • The new LPECC upper bound is strictly stronger than Zhao and Zhang’s whenever both bounds apply.Its asymptotic tightness follows from the asymptotic tightness of the CPECC constructions.Source: §5 · p. 22
  • The previous quadratic-order weight requirement is reduced to order t^3/2 for both CPECC and LPECC codes.The conclusion identifies this result for e = w−3 in the considered parameter ranges.Source: §5 · p. 22
  • For fixed t and w in the respective parameter ranges, the maximum sizes of both code types have determined asymptotic sizes.The conclusion attributes the proofs to uniform and mixed-weight 3-shadow bounds.Source: §5 · p. 22
Loading 2609.35061v1…