Binärcode mit Einschränkung

Angenommen, ich habe ein Alphabet mit n Symbolen. Ich kann sie effizient mit codieren$\lceil \log_2n\rceil$-bits Strings. Zum Beispiel, wenn n = 8:
A: 0 0 0
B: 0 0 1
C: 0 1 0
D: 0 1 1
E: 1 0 0
F: 1 0 1
G: 1 1 0
H: 1 1 1

Jetzt habe ich die zusätzliche Einschränkung, dass jede Spalte höchstens p Bits enthalten muss, die auf 1 gesetzt sind. Zum Beispiel für p = 2 (und n = 8) ist eine mögliche Lösung:
A: 0 0 0 0 0
B: 0 0 0 0 1
C: 0 0 1 0 0
D: 0 0 1 1 0
E: 0 1 0 0 0
F: 0 1 0 1 0
G: 1 0 0 0 0
H: 1 0 0 0 1

Gibt es bei n und p einen Algorithmus, um eine optimale Codierung (kürzeste Länge) zu finden? (und kann bewiesen werden, dass es eine optimale Lösung berechnet?)

BEARBEITEN

Bisher wurden zwei Ansätze vorgeschlagen, um eine Untergrenze für die Anzahl der Bits abzuschätzen $m$. Ziel dieses Abschnitts ist es, eine Analyse und einen Vergleich der beiden Antworten bereitzustellen, um die Auswahl der besten Antwort zu erläutern .

Yuvals Ansatz basiert auf Entropie und bietet eine sehr schöne Untergrenze:$\frac{logn}{h(p/n)}$ wo $h(x) = xlogx + (1-x)log(x)$.

Alex 'Ansatz basiert auf Kombinatorik. Wenn wir seine Argumentation etwas weiterentwickeln, ist es auch möglich, eine sehr gute Untergrenze zu berechnen:

Gegeben $m$ die Anzahl der Bits $\geq\lceil log_2(n)\rceil$gibt es eine einzigartige $k$so dass Man kann sich davon überzeugen, dass eine optimale Lösung das Codewort mit allen niedrigen Bits verwendet, dann die Codewörter mit 1 Bit hoch, 2 Bit hoch, ..., k Bits hoch . Für die verbleibenden zu codierenden Symbole ist überhaupt nicht klar, welche Codewörter optimal verwendet werden sollen, aber mit Sicherheit die Die Gewichte jeder Spalte sind größer als sie wären, wenn wir nur Codewörter mit Bit hoch verwenden könnten und für alle . Daher kann eine untere Grenze mit

$$1+\binom{m}{1} + ... +\binom{m}{k} \lt n \leq 1+\binom{m}{1} + ... + \binom{m}{k}+\binom{m}{k+1}$$ $n-1-\binom{m}{1}-...-\binom{m}{k}$$w_i$$k+1$$|w_i - w_j| \leq 1$$i, j$$p=max(w_i)$ $$p_m = 0 + 1 + \binom{m-1}{2} +... + \binom{m-1}{k-1} + \lceil \frac{(n-1-\binom{m}{1}-...-\binom{m}{k}) (k+1)}{m} \rceil$$

Versuchen Sie nun mit und , zu schätzen . Wir wissen, dass , wenn also , dann . Dies ergibt die Untergrenze für . Berechnen Sie zuerst den und finden dann das größte so dass$n$$p$$m$$p_m \leq p$$p \lt p_{m'}$$m' \lt m$$m$$p_m$$m'$$p \lt p_{m'}$

Dies ist, was wir erhalten, wenn wir für die beiden unteren Grenzen zusammen zeichnen, die untere Grenze basierend auf der Entropie in Grün, diejenige basierend auf der kombinatorischen Argumentation oben in Blau, erhalten wir:$n=1000$

Beide sehen sich sehr ähnlich. Wenn wir jedoch den Unterschied zwischen den beiden unteren Grenzen darstellen, ist es klar, dass die untere Grenze, die auf kombinatorischen Überlegungen basiert, insgesamt besser ist, insbesondere für kleine Werte von .$p$

Ich glaube, dass das Problem von der Tatsache herrührt, dass die Ungleichung schwächer ist, wenn kleiner wird, weil die einzelnen Koordinaten mit kleinem korrelieren . Dies ist jedoch immer noch eine sehr gute Untergrenze, wenn .$H(X) \leq \sum H(X_i)$$p$$p$$p=\Omega(n)$

Hier ist das Skript (python3), mit dem die unteren Grenzen berechnet wurden:

from scipy.misc import comb
from math import log, ceil, floor
from matplotlib.pyplot import plot, show, legend, xlabel, ylabel

# compute p_m 
def lowerp(n, m):
  acc = 1
  k = 0
  while acc + comb(m, k+1) < n:
    acc+=comb(m, k+1)
    k+=1

  pm = 0
  for i in range(k):
    pm += comb(m-1, i)

  return pm + ceil((n-acc)*(k+1)/m)

if __name__ == '__main__':
  n = 100

  # compute lower bound based on combinatorics
  pm = [lowerp(n, m) for m in range(ceil(log(n)/log(2)), n)]
  mp  = []
  p = 1
  i = len(pm) - 1
  while i>= 0:
    while i>=0 and pm[i] <= p: i-=1
    mp.append(i+ceil(log(n)/log(2)))
    p+=1
  plot(range(1, p), mp)

  # compute lower bound based on entropy
  lb = [ceil(log(n)/(p/n*log(n/p)+(n-p)/n*log(n/(n-p)))) for p in range(1,p)]
  plot(range(1, p), lb)

  xlabel('p')
  ylabel('m')
  show()

  # plot diff
  plot(range(1, p), [a-b for a, b in zip(mp, lb)])
  xlabel('p')
  ylabel('m')
  show()

Es gibt eine zusätzliche Untergrenze, die wir erstellen können und die Fälle wie das behandelt, was @ user3017842 in ihrem Kommentar zu Yuvals Antwort erwähnt hat. (Fälle, in denen besonders klein ist.) Angenommen, wir wussten bereits: Dann haben wir über alle Codewörter hinweg insgesamt hohe Bits. Da wir an den Fällen interessiert sind, in denen klein ist, betrachten wir diese hohen Bits als unsere begrenzende Ressource und möchten damit einen Code erstellen (und sehen, wie viele Codewörter wir möglicherweise herausholen können). Wir können 1 Codewort mit allen Nullen haben, dann Codewörter mit einer einzelnen 1, dann mit zwei Einsen usw. Wenn wir die höchste Anzahl von Bits in einem Codewort aufrufen , dann $p$$m$$pm$$p$$m$$m \choose 2$$k$

$$pm = 0\cdot 1 + 1\cdot m + 2\cdot {m \choose 2}+... \le \sum_i^k i{m \choose i}$$ Während unsere Anzahl von Codewörtern in ähnlicher Weise durch wenn wir den Fall betrachten, in dem , dann ist bereits durch die erste Ungleichung impliziert. ( ). Dann würde der Code aus dem Wort single-$n$ $$n \le \sum_i^k {m \choose i}$$ $p \le m$$k \le 2$$pm = m^2 = m + 2{m \choose 2}$$0$$m$$1$ -words und zweirädrigen -words. Also oder invertieren von Dies ergibt die enge Untergrenze von$(p-1)m/2$$1$ $$n \le 1 + m + (p-1)m/2$$ $$m \ge \frac{2(n-1)}{p+1} .$$ $m\ge 5$ auf dem Beispiel, das Sie zur Verfügung stellen, aber wie bereits erwähnt, wird wahrscheinlich nur währenddessen sehr nützlich sein $p \approx m$ (oder ).$p \approx \sqrt n$

Hier ist eine Untergrenze und eine asymptotisch übereinstimmende Konstruktion, zumindest für einige Bereiche der Parameter. Bezeichnen Sie die Anzahl der Spalten mit und nehmen Sie der Einfachheit halber an, dass$m$$p \leq n/2$ .

Wir beginnen mit einer Untergrenze für . Sei die Kodierung des Symbols, das gleichmäßig zufällig ausgewählt wird. Sei die einzelnen Koordinaten und sei das Gewicht der ten Spalte. Dann ist Daher Hier ist die Entropie einer Zufallsvariablen und ist die Entropiefunktion . (Sie können eine beliebige Basis für den gewünschten Logarithmus verwenden.)$m$$X$$X_1,\ldots,X_m$$w_i \leq p$$i$

$$\log n = H(X) \leq \sum_{i=1}^m H(X_i) = \sum_{i=1}^m h(w_i/n) \leq m h(p/n).$$ $$m \geq \frac{\log n}{h(p/n)}.$$ $H$$H(X) = -\sum_x \Pr[X=x] \log \Pr[X=x]$$h$$h(x) = -x\log x-(1-x)\log(1-x)$

Die asymptotisch übereinstimmende Konstruktion, die für funktionieren sollte , wählt ein bisschen größer als diese Untergrenze und wählt ein zufälliges Codierungsschema, wobei jedes Bit mit einer Wahrscheinlichkeit die ein Bit ist, auf gesetzt wird kleiner als . Wenn wir die Parameter richtig auswählen, sollten wir feststellen, dass dies mit positiver Wahrscheinlichkeit zu einer legalen Codierung führt (alle Codewörter sind unterschiedlich und alle Spaltengewichte sind höchstens ).$p = \Omega(n)$$m$$1$$q/n$$p/n$$p$

Hier ist eine einfache Suchmethode. Wir gehen von einer Untergrenze für die Anzahl der Bits aus und versuchen dann, eine legale Codierung zu finden. Speziell.

Sei m die aktuelle Anzahl von Bits. Codiere das Symbol i als bi1, bi2, ..., bim.

Einschränkungen: bi xor bj ist nicht 0 - mit anderen Worten, die Codierung jedes Symbols ist eindeutig

Für alle j: sum_i bij <= p.

Dies ist ein pseudo-boolesches Erfüllbarkeitsproblem (gut, es kann leicht als Standard-Erfüllbarkeitsproblem codiert werden). Erhöhen Sie also einfach m weiter, bis Sie eine finden, die zufriedenstellend ist (oder führen Sie eine binäre Suche mit unteren und oberen Grenzen durch, um das minimale m zu finden).

Dies garantiert natürlich nicht, dass Sie in der Praxis tatsächlich das minimale m finden können, der SAT-Check könnte eine Zeitüberschreitung verursachen.