2019年 10月 22日

標準符号化試験信号 PN符号 LFSR

tech

別表第35とかに出てくる「標準符号化試験信号」の生成について調べた。

擬似信号発生器は、標準符号化試験信号（ＩＴＵ－Ｔ勧告Ｏ．150による９段ＰＮ符号）を発
生させる。と書いてある。

ITU-T O.150 は n 段(stage)のシフトレジスタで構成されるテスト用の疑似乱数列について定義している。n段の符号はnビットのシフトレジスタに対応する。

具体的な生成方法は wikipedia の LFSR を読むのがわかりやすい。

9段のPN符号

「4.1 511-bit pseudo-random test pattern」となっているところが9段のもの。

「The pattern may be generated in a nine-stage shift register whose 5th and 9th stage outputs are added in a modulo-two addition stage, and the result is fed back to the input of the first stage. The pattern begins with the first ONE of 9 consecutive ONEs.」と文章で書いてある。

5th and 9th と書いてあるところが帰還多項式に対応しており、この場合

になる。また初期状態も定められており、全ビット1から初めるとしている。

JavaScript での実装

以下のような任意のビット数(ただし32ビット以下)の LFSR のコードを書いた。全ビットが0でない限りは最大周期で全ての状態が出現する。

/**
 * Linear-feedback shift register
 *
 * reg: n bits register state
 * n: Bits(n) (up to 32bits)
 * taps: feedback polynomial (eg. x^16 + x^14 + x^13 + x^11 + 1 => [16, 14, 13, 11])
 * ref. https://en.wikipedia.org/wiki/Linear-feedback_shift_register
 */
function LFSR(reg, n, taps) {
	const mask = n === 32 ? (-1>>>0) : (1 << n) - 1;
	reg &= mask;

	const bit = taps.
		map( (tap) => reg >> (n - tap) ).
		reduce( (r, i) => r ^ i ) & 1;

	return ( (reg >>> 1) | ( bit <<  (n-1) ) ) & mask;
}

const start = 511;
let lfsr = start;
let period = 0;
do {
	lfsr = LFSR(lfsr, 9, [9, 5]);
	console.log('output:', lfsr>>(9-1), 'internal:', (lfsr | (1<<9)).toString(2).slice(1));
	period++;
} while(lfsr !== start);
console.log('this feedback polynomial period:', period);

関連エントリー