Wikipedia の LDPC の項だけ読むとそんな難しくなさそうに見えるけど、実際に実装しようと思うと、むちゃくちゃ難しい。

H行列 (パリティ検査行列) が難しい

LDPC符号の設計では、性能に優れたパリティ検査行列(H行列)を用意するのがまず難しい。ここにいろんな要素がある。

  • 正則(regular)か(各ノードの次数が一定)
  • 構造的な性質(たとえば巡回構造をもつ QC-LDPC など)を持つか (復号効率に影響する)
  • 系統的符号化 が可能な構造(systematic) を持つか(これは生成行列側の問題)
  • girth(ループの最小長): Tannerグラフにおいて短いサイクルは復号性能を劣化させるため、girthが大きい方が望ましい。

数学的素養がないと難しすぎる。そして自力で設計するのは考えたくない。

Protographが難しい

そんなH行列、例え1つ設計できたとしても、任意のデータ長・符号化率を持つH行列をいくつも作ろうと思うと何倍も大変になってしまう。

そこで Protograph (原始グラフ) という性質の良い原型となるような小さなグラフをまず設計し、それを何らかの方法で拡大して任意の大きさのH行列を得るという設計方法がある。

パンクチャリングが難しい

パンクチャリングは性質の良いH行列を使うために,多少の計算効率を犠牲にしつつ柔軟な送信ビット長/符号化率を得るための方法といえる

良い性質の Protograph を得られたとしても、それを拡大するプロセスには制約がある。整数倍の行列しか作れないとか。

そうなると求めるデータ長・符号化率ぴったりの行列というのは結局作れない。

これを解決するのがパンクチャリング。符号化率の低い(0.4など)のProtographを拡大し、欲しい符号化率 (0.5など)になるまでパリティビットの一部を送信しないことで、ちょうどいいサイズを作れる。

ぴったりよりも大きい行列を使うので計算コストは増えるが、高性能なH行列設計を流用できるという利点がある。

エンコードもデコードも難しい

エンコードは既知の操作するだけやろ? という気持ちを打ち砕く。どっちも難しい。なんならデコードのほうが簡単かもしれない

  • エンコードは生成行列(G行列)を得る必要がある。任意のH行列に対してG行列を導出するのが難しい。
  • デコードには、確率伝播(Belief Propagation)アルゴリズムに基づく Sum-Product 法や、近似的な Min-Sum 法などがある。どちらもTannerグラフ上での繰り返し計算を必要とし、実装や収束性で難しい
  1. トップ
  2. tech
  3. LDPC難しすぎる

performance.now() が monotonic (単調増加) なことを利用すると、システム時計の変化を比較的高精度に得られるなと思ったので、以下のようなClockMonitorクラスを作ってみた。

// ClockMonitor: システム時計の大幅な変更(NTP補正・手動変更等)を検知し、イベントを発行するクラス
// WebAudioやperformance.now()はmonotonicな経過時間だが、絶対時刻(Date.now())はシステム時計依存でジャンプすることがある
// そのため、performance.timeOrigin+performance.now()で絶対時刻を計算している場合、
// システム時計が変化しても自動で補正されない(ズレたままになる)
// このクラスは、定期的にDate.now()とperformance.timeOrigin+performance.now()の差分を監視し、
// 一定以上の差分が発生した場合に"clockchange"イベントを発行することで、
// 利用側がoffset等を補正できるようにする
class ClockMonitor extends EventTarget {
	constructor({ threshold = 2000, interval = 1000 } = {}) {
		super();
		this.threshold = threshold; // 何ms以上の差分で検知するか
		this.interval = interval;   // 監視間隔(ms)
		this.offset = performance.timeOrigin || 0; // performance.now()の起点(初期化時の絶対時刻)
		this._timer = null;
	}

	start() {
		if (this._timer) return;
		this._timer = setInterval(() => {
			const perfNow = performance.now();
			const now = Date.now();
			// 現在の絶対時刻の期待値(初期offset+経過時間)
			const expected = this.offset + perfNow;
			const diff = now - expected;
			// threshold以上の差分が出たらシステム時計変更とみなす
			if (Math.abs(diff) > this.threshold) {
				// offsetを補正し、イベント発行
				this.offset += diff;
				this.dispatchEvent(new CustomEvent("clockchange", {
					detail: { offset: this.offset, diff }
				}));
			}
		}, this.interval);
	}

	stop() {
		if (this._timer) {
			clearInterval(this._timer);
			this._timer = null;
		}
	}
}

他の方法

Date.now() を単に保持しておいて比較することでも、過去への遡りは検出できる。が、未来へ進むのは検出できない (ただのタイマーの遅れと区別できない)

問題点

問題点: performance.now() は monotonic ではあるがスリープで時間の連続性が失われることがある
仕様上は連続することになっているが、一部の環境のブラウザだけ。

  1. トップ
  2. tech
  3. JSでシステム時計の変化(時刻変更、NTP同期)を検知する

micro-template.js という2012年に作った embed JS 的なテンプレート処理ライブラリがある。コピペできるぐらい小さくて、早いことがコンセプト。

完全に放置してたけど、ちょっと手を入れはじめたらいろいろやりたくなってしまったので、だいぶ改修をいれてしまった。

  1. トップ
  2. tech
  3. micro-template.js を13年ぶりにいろいろいじった