http//pulsar.blog.ocn.ne.jp/bonsai/sys-s.pdf------------------------------------------------------------2012.08
Supplements to Integrated Examples on
Discrete Systems
whypulsar@coffee.ocn.ne.jp------------------------------------------------------------------------------©2011.06
3#80: 補遺一覧
[C6D%]巡回符号の復号，
sys-s.pdf に関する日付順の補遺の一覧を示
#85: 非線形制御
す．記号は(一般に通用しないものも含め)原則
未
として sys-s.pdf に準じる．追加事項は，
#86: オートマトン
(1) [ymd%s] の「ymd」は 0,･･･,9,A,･･･,Z に
未
よる日付．
「s」は 0,･･･,9,A,･･･,Z の系列の
#87: 関連資料
辞書式配列によるラベル．
(1) math-s.pdf 内
(2) 引用は「site$file」，「authors$title」，
「ymd%title」等に URL を貼り付け．ただし
本資料内の補遺は URL を省略．
(3) ヘッダの日付は最終更新日．
2
2
(4) {t }t は x (t ) = t である写像 x の意味．
(T {t 2 }t )(s ) はT {t 2 }t (s ) と略すが，(Tx )(s )
をTx (s ) とは略記しない．
#81: 信号の空間
[B6F%]いろいろな空間，[B6L%]確率の表現，
#82: 通信網
[B6U%]グラフ理論の応用，[B72%]離散情報の符
号化，
#83: ディジタルフィルタ
[BAF%]ラプラス変換，[BAK%]ｚ変換，[BAR%]
フーリエ変換，[BAV%]２次元の信号，[C74%]
ハール･ウェーブレット，[C7S%]デルタ関数，
#84: 巡回符号
[1#未%]ルベーグ積分，[1#B91%]初等関数，
2011-10-12
B6F%0: いろいろな空間
E n の点は a1e1 + " + anen ，２点 a1e1 + " +
元の間に遠近がある集合を空間(位相空間)，こ
anen と b1e1 + " + bnen の間の距離は
(a1 − b1 )2 + " + (an − bn )2
の集合の元を点という．
[1] Wikipedia$空間／幾何学における空間．
である．
[2] Wikipedia$直線／座標
%3: ベクトル空間
[3] Wikipedia$ユークリッド空間
和とスカラー倍が定義された空間をベクトル
[4] Wikipedia$ベクトル空間(線形空間)
空間(線形空間)という．[#11]のアナログ信号
[5] Wikipedia$計量ベクトル空間(内積空間)
の集合もベクトル空間になりうる．ただし，す
[6] Wikipedia$コーシー列
べてのアナログ信号を含めると議論しにくく
[7] Wikipedia$ヒルベルト空間
なるので，通常は適当な制限条件(具体例は割
%1: 数直線
愛)を設ける．
直線上に原点 O ，単位点 E を定め，直線上の
%31: (@11)での説明は通常の定義より限定さ
点 P の座標を， OP が OE と同じ向きのとき
れている(信号処理では x i を複素数値の関数，
JJJG
JJJG
は OP / OE ，逆向きのときは − OP/ OE とす
る．各点が座標をもつ直線を数直線という．
%2: ユークリッド空間
ak も複素数で考えることが多い)．
%4: 内積空間
ベクトル空間の任意の元 w , x , y とスカラー
a に対して内積 (x, y ) が
古典物理学や中学の数学でいう空間は３次元
3
のユークリッド空間 E である．例えば，地上
(1) (x, x ) ≥ 0 ，かつ x = 0 ⇔ (x, x ) = 0
(2) (x, y ) = (y, x ) ( (y, x ) の共役複素数)
の１点 O を原点とし，東向きに x 軸，北向き
(3) (w + ax, y ) = (w, y ) + a(x, y )
に y 軸，上向きに z 軸をとる．各軸は数直線で，
を満足する複素数として定義されているとき，
点 P1 = (x 1, y1, z 1 ) の x 1 は P1 の x 軸への垂線
この空間を内積空間という．
の足の x 座標である．y1 ，z 1 についても同様．
%41: 複素数値のアナログ信号の場合
E 3 内の２点 (x 1, y1, z 1 ) ， (x 2 , y2 , z 2 ) 間の
2
2
2
(x , y ) =
∫
∞
−∞
x (t ) y(t )dt
距 離 は (x 1 − x 2 ) + (y1 − y2 ) + (z 1 − z 2 )
%5: ヒルベルト空間
で定義され，ピタゴラスの定理が成立する．
内積空間の任意の元 x , y の距離を
3
%11: E は一種のベクトル空間である．上記
の (x 1, y1, z 1 ) のような表現では n 次元のユー
n
x − y = (x − y, x − y )
で定める．この距離で任意のコーシー列(収束
クリッド空間 E の点に拡張しにくいので，単
する点列)が空間内の点に収束するとき，この
位ベクトル e1 = (1, 0, 0) ， e2 = (0, 1, 0) ，
空間をヒルベルト空間という．
e 3 = (0, 0, 1) を用いて， a = (a1, a2 , a 3 ) を
%51: ベクトル x の大きさ(ノルム)は x と 0 の
a = a1e1 + a2e2 + a 3e3 と表わすことも多い．
距離であり， x で表わす．
この表現によれば n 次元のユークリッド空間
x ≠ (x, x ) で
あるノルムの例は x = x 1 + " + x n ．
2011-06-22
B6L%0: 確率の表現
写真のデータを標本化すると有限次元のユー
[1] ichiro$06bpr.pdf(確率論基礎)
クリッド空間の点となり，さらに標本値を量子
[2] yasutaka$tutorial1.pdf(確率過程 30 講)
化すれば有限集合になる．
[3] Wikipedia$確率空間／English
%2: 確率変数
[4] Wikipedia$確率変数／$確率論
事象に対応させた数値(ベクトルでもよい)を
[5] Wikipedia$確率分布
とる変数を確率変数という．例えば，ある地点
[6] Wikipedia$確率過程／English
の明日正午の気温(単位 °C )の確率変数を X
%1: 確率空間
とし， 15 < X ≤ 16 である確率を考えること
確率論では (Ω, S , P ) のように表わされる確
ができる．事象に対応させる数値が便宜的な場
率空間を考える． Ω は標本空間で確率を考え
合は確率変数を考えても活用できない(電話番
ている事象(出来事)の集合である，S は確率を
号の平均値や分散は無意味)．
計算できる Ω の部分集合の“適当な”集合で，
%3: 確率分布
A ∈ S (⊆ 2Ω ) である A の確率は P (A) で表わ
X が実数値の確率変数であるとき，
される．P : S → [0, 1] は確率測度とよばれる
F (x ) = Pr(X ≤ x )
写像で，次の条件を満たす．
で定められる F (x ) を X の確率分布関数とい
(1) P (Ω) = 1
う．X の値が離散的であれば F (x ) は階段的に
(2) A ， B が共通部分のない S の元であれば
変化する． F (x ) が微分可能なとき，その導関
P (A ∪ B ) = P (A) + P (B ) (A ∪ B ∈ S )
%11: 上記の“適当な”の意味は(%12)参照． S
Ω
は通常 F の筆記体で表わす．なお， 2 は Ω の
すべての部分集合の集合で， Ω から {0, 1} へ
Ω
の写像の集合 {0, 1} に対応している．
%12: Ω = {a, b, c} のとき，S = {φ, {a, b},
{c}, Ω} でもよいが， P ({a, b}) + P ({c}) =
P (Ω) でなければならない．また {a } も S に加
数 p(x ) = F ′(x ) を確率密度関数という．
%31: 微小な Δx ， Δy に対して
Pr(x < X ≤ x +Δx ∧ y <Y ≤ y +Δy )
≈ p(x , y )Δx Δy
と近似できれば，p(x , y ) は (X , Y ) の確率密度
関数である(表現は正確でない)．このとき
E [(X , Y )] =∫
∞
−∞
∫
∞
−∞
(x , y ) p(x , y )dx dy
%4: 確率過程
えたければ S = 2 にせねばならない．
(Yn , Yn −1 ) を (y(n ), y(n − 1)) (y ∈ Ω) の２次
%13: [#15](1)排反事象,(2)独立事象,(3)条件
元確率変数と考えると，信号を介して確率変数
付き確率参照．条件付き確率の定義により
の性質を検討することになり具体化しづらい．
Ω
P (A)P (B | A) = P (B )P (A | B )
このため，通常は時刻をパラメータとする確率
%14: Ω を顔の写真の集合とする．全く同じ顔，
変数の列(無限次元の確率変数)で考える[2]．
表情はないので(試行によってある顔の写真が
%41: [#17]のような単純マルコフ情報源に限
出現する事象の)確率は無限小で扱いにくいが，
定すれば状態遷移確率行列で十分．
2011-07-01
B6U%0: グラフ理論の応用
意味するときは有向グラフ，「 v1 と v2 は親子
グラフ理論で扱うグラフは二項関係である．
である」を意味するときは無向グラフとなる．
[1] j_inoue$GRAPH2007.pdf
%22: 木を無向グラフの一種とする説明もある
[2] Wikipedia$グラフ理論
が，計算機科学で用いる二分木の枝には向きが
[3] Wikipedia$二項関係
あり，さらに左の子，右の子の区別もある．
[4] Wikipedia$順序集合
%23: グラフ (V , E ) が木のとき，(v1, v2 ) ∈ E
[5] Wikipedia$二分木
を v1 ≤ v2 で表わすと，(V , ≤) は半順序集合で
[6] Wikipedia$ダイクストラ法
あり， v1 から v 3 への経路が存在することを
[7] Wikipedia$最大フロー問題
v1 ≤ v 3 で表現できる．
[8] Wikipedia$状態遷移図
%3: ネットワーク
[9] Wikipedia$Signal-flow_graph
グラフは通信網，交通網，電気回路網等での接
%1: 二項関係
続関係の表現に便利である．隣接行列を m 乗
集合V の元 v1 ，v2 がある関係 E を満たすこと
した行列の (i, k ) 要素は m 本の枝を通って節
を (v1, v2 ) ∈ E で表わすと， E ⊆ V ×V であ
点 vi から節点 vk に行く経路の数に等しい．
り，[#20]のようなV の元を節点，(v1, v2 ) ∈ E
%31: 隣接行列の他に，枝の始点と終点を示し
を枝 e12 = (v1, v2 ) で表わした図が得られる．
た接続行列もよく用いられる．
%11: 電気回路のグラフでの枝の向きは電流の
%32: (#23)で言及した最短経路問題の解法と
向きを示し，逆向きにしても電流の符号が反転
してダイクストラ法がある．
するだけである．一方，状態遷移図の枝の向き
%33: 各枝の容量を定め，始点から終点への最
は遷移の可否を意味し，逆向きにはできない．
大フローを求める問題を最大フロー問題とい
枝の向きを反転できる「便宜的な」有向グラフ
う．
「最大フローは最小カットの容量に等しい」
では，経路は隣接する節点の系列である．
という定理がある．
%12: 任意の２節点間に経路が存在するグラフ
%4: その他
を連結グラフという(枝の向きに従った経路の
以下は sys.pdf の参照番号・内容未定のため後
場合は「強連結」ということが多い)．
日追加します．
%2: 木
・状態遷移図
V を人間の集合， (v1, v2 ) ∈ E を「 v1 は v2 の
・シグナルフロー・グラフ
親である」としてグラフを描くことができる．
法律的でなく生物学的な親子関係で考えれば，
このグラフには閉路は存在しない．閉路のない
連結グラフを木という．
%21: (v1, v2 ) ∈ E が「 v1 は v2 の親である」を
2011-08-15
B72%0: 離散情報の符号化
(− log2 qi ) の２値系列に符号化できれば，平均
シャノンの情報理論の主要部分である情報源
符号語長は情報源のエントロピーをビットで
符号化と通信路符号化について説明する．
表わした値のほぼ 5 倍になる．
[1] Wikipedia$情報理論
%21: 「符号化できれば」とは符号化された S 2
[2] Inoue$2115/772(講義資料集)
の系列から元の S 3 の系列が一意に復号できる
5
InfoTheory05_8.pdf：通信路符号化定理
ことを要求している．[#27]のハフマン符号は
一意に復号可能である．また
[3] yobology$channel_coding.htm
[-] Shannon$BSTJ(歴史的論文)
− log2 0.45 ≈ 1.152 ≈ 1
(0)
[-] Uyematsu$vol4no2_123.pdf(展望)
− log2 0.27 ≈ 1.889 ≈ 2
(10)
[-] Uyematsu$vol1no1_08.pdf(展望)
− log2 0.15 ≈ 2.736 ≈ 3
(111)
%1: 離散情報の情報量
− log2 0.13 ≈ 2.943 ≈ 3
(110)
[#14]の任意の n について Pr(X n = ai ) = pi
であり，平均符号語長は 1.830 で，情報源のエ
である {a1, a 2 , a 3 } を出力する(定常的な)情
ントロピー 1.822 [ビット]の値に近い．
報源について考える．情報量を I i = − log pi
%22: エントロピーが H である情報源の出力を
と定めたのは，単に珍しい事象ほど情報量が大
m 値の系列に符号化するとき，情報源１記号
きいというだけでなく，自然な性質
当たりの長さを logm H + ε ( ε は任意の正数)
H (X n−1, X n ) = H (X n −1 ) + H (X n | X n−1 )
にできるが， logm H 以下にはできない．
も成立するためである(#25)．エントロピー
%3: 通信路符号化
H (X n ) は p1 = p2 = p3 のときに最大になる．
記号 0 ，1 を k [個／秒]で伝送する雑音のある
%2: 情報源符号化
通信路の誤り率を p [回／秒]とする．この通信
0 ，1 の系列を伝送する通信路で(%1)の ai の系
路で１秒当たりに伝送できる情報量の最大値
列を送る場合を考え，S 3 = {a1, a2 , a 3 } ，S 2 =
C (通信路容量)は，
{0, 1} とおく．１対１写像 f : S 3 → S
2
2
f (a1 ) = 01 ， f (a2 ) = 10 ， f (a 3 ) = 11
による単純な符号化は無駄が多いが，
であり，伝送速度がC より小さい 0 ，1 の系列
は適当に符号化すれば誤り率を任意の正数 ε
0 < 28 − 35 = 256 − 243 28
5
3
C = k (1 + p log2 p + (1 − p)log2 (1 − p))
より小さくできる．
8
2
に注目して，g : S → S で符号化すると無駄
%31: 通信路容量は入力側の信号を変えたとき
が減少する．とくに p1 = p2 = p3 のランダム情
の入出力間の相互情報量の上限であり，伝送速
−5
報源の場合，平均符号語長は log2 3
≈ 7.92
であるから，符号化効率は 7.92 / 8 ．
ランダム情報源でない場合も，確率 qi で現わ
5
れる S 3 の元 wi に対して， wi を長さがほぼ
度は１秒当たりに伝送する情報量である．
%32: (%3)の「適当に符号化」は，伝送速度を R
とおいて，語長がほぼ nR の系列を語長がほぼ
nC の系列に符号化し， n → ∞ とする．
2012-09-30
(Lx )(s ) =
BAF%0: ラプラス変換
微分方程式をラプラス変換すると代数方程式
になる．
だから x (t ) = x (0)e
−at
(t ≥ 0) ．
%31: 通常 t < 0 での x (t ) の値は分からない
[1] Wikipedia$ラプラス変換
[2] BAR%フーリエ変換
%1: 定義
信号 x の(片側)ラプラス変換 (Lx )(s ) を
(Lx )(s ) =
x (0)
= x (0)(Lu)(s + a )
s +a
∫
∞
0
x (t )e −st dt
から， t ≥ 0 を当然として省略する．
%32: %3 の a は複素数でもよい．したがって
1
= L{e ∓iωt }t (s )
s ± iω
%33: L
{∫
t
0
}
1
x (t )dt (s ) = (Lx )(s )
s
t
で定義する([#30]等と異なり x は連続信号)．
%4: 伝達関数
また，命題 X の関数 Φ を用いて，関数 u を
線形時不変な回路の入力 u に対する出力をそ
⎪⎧1 (X = T)
u(t ) = Φ(t ≥ 0) ， Φ(X ) = ⎪⎨
⎪⎪0 (X = F)
⎪⎩
の回路のステップ応答，ステップ応答の導関数
で定め， x : R → R ，(Lx )(s ) ， Lx : C → C を
変換を伝達関数という．インパルス応答が h で
それぞれ {x (t )}t ，L{x (t )}t (s ) ，{(Lx )(s )}s で
ある線形時不変な回路に x が入力されたとき
表わす( Lx は解析接続して考える)．ただし，
この記法は一般には通用しないことに注意．
%11: 定義式の積分が可能な x の集合について
2
考える．例えば exp(t ) は対象外である．
%2: 公式
の出力は h ∗ x であり，
(L(h ∗ x ))(s ) = (Lh )(s )(Lx )(s )
%14: 関数 δh (h > 0) を
δh (t ) =
u(t ) − u(t − h )
h
で定めると， h ≈ 0 のとき (Lδh )(s ) ≈ 1 で，
x ， y を信号， a ， b を実数とすると
L(ax + by ) = aLx + bLy
d
L
x (t ) (s ) = s(Lx )(s ) − x (0)
dt
t
{
をインパルス応答，インパルス応答のラプラス
}
L{x (t − a )u(t − a )}t (s ) = e −sa (Lx )(s )
L{e −at x (t )}t (s ) = (Lx )(s + a )
また
(x ∗ y )(t ) =
∫
∞
−∞
x (t − t )y(t )dt
で定義される畳み込み x ∗ y に対して
(L(x ∗ y ))(s ) = (Lx )(s )(Ly )(s )
%3: 計算例
d
x (t ) = −ax (t ) とすると
dt
s(Lx )(s ) − x (0) = −a(Lx )(s )
∫
∞
−∞
x (t )δh (t − a )dt ≈ x (a ) ( a < 0 可)
%5: 逆ラプラス変換
(Lx )(s ) = X (s ) である x を X の逆ラプラス
−1
変換といい， L X で表わす．例えば
⎧10s 2 + 18 ⎪
⎫
⎪
⎪
L−1 ⎪
⎨ 3
⎬ (t )
⎪
⎪
+
s
9
s
⎪
⎪s
⎩
⎭
2
4
4
= L−1 +
+
s s + 3i s − 3i
= 2 + 2 cos(3t )
{
} (t)
s
%51: X (s ) が Re s ≥ α で正則であれば
(L−1X )(t ) =
α +iβ
1
X (s )est ds
lim ∫
β
→∞
α
β
−
i
2πi
である．x の不連続点 t0 での Lx の逆ラプラス
変換の値は
1
{x (t0 − 0) + x (t0 + 0)} ．
2
2012-09-30
G
G −n
z +1 G
x0
(An x )z =
(Z x )(z ) −
∑
2
2
n =0
∞
BAK%0: ｚ変換
差分方程式をｚ変換すると代数方程式になる．
であるから，%1 の離散近似によって
[1] Wikipedia$Z変換
[2] BAF%ラプラス変換
[3] BAR%フーリエ変換
%1: 微分方程式の近似
G
G
⎛
G
G
x0
x 0 ⎞⎟
⎜
Δ(z )(Zx )(z ) − =G ⎜A(z )(Zx )(z ) − ⎟⎟
⎜⎝
h
2⎠
G
G
v0
+ A(z )(Zv )(z ) −
2
z −1
z +1
， A(z ) =
Δ(z ) =
h
2
h を微小な正の数とする．線形常微分方程式
G
G
G
x ′ (t ) = G x (t ) + v(t )
が得られる．
を考え，便宜的な記法として行列G の (i, k ) 要
%31: y ′′(t ) + ay ′(t ) + by(t ) = 0 のとき，
Gi
G
素を [G ] ，x の第 i 要素を [x ]1 で表わす[1#53]．
G
G
G
G
x n = x (nh ) ， v n = v(nh ) とおき，
G
G
G
G
G x n +1 − x n
G x n +1 + x n
， An x =
Δn x =
h
2
i
k
を用いた t = nh + h /2 における離散近似
G
G
G
Δn x = G An x + An v
G
から x n +1 を求める方法は陰的修正オイラー法
⎛yn′ +1/ 2 ⎞⎟
⎛0
1 ⎞⎟ G
⎜⎜
⎟⎟ ≈ Δ xG = ⎜⎜
⎟
⎜⎜
n
⎜⎜−b −a ⎟⎟⎟ An x
⎟
⎜⎝yn′′+1/ 2 ⎠⎟
⎝
⎠
2
2
と近似すると Δn y + a Δn An y + bAn y = 0 ．
%32: 双１次変換
s=
Δ(z ) 2 z − 1
= ⋅
A(z ) h z + 1
と等しい．また Δn An = An Δn が成立する．
は s 平面の虚軸を z 平面の単位円に対応させ
%11: x ′ (t ) =G (t )x (t ) + v(t ) で はｚ 変換 を使
るから，x ′′(t ) + ω x (t ) = 0 を%1 のように離
G
G
G
G
2
えないのでGn +1/ 2 , v n +1/ 2 を用いる方がよい．
散近似した解も振幅は一定である(４次の陽的
%2: 両側ｚ変換
ルンゲクッタ法の近似解は発散する)．
Gi
Gi
[#33]の片側ｚ変換 Z を [Zx ]1 = Z[x ]1 と拡張し， %4: 逆ｚ変換
(Zy )(z ) = Y (z ) で あ る y を Y = {Y (z )}z の
同様に定義される
G
(Zi x )(z ) =
∞
G
∑x
n
−1
z −n
逆ｚ変換といい， Z Y で表わす(BAF%1)．
n =−∞
を両側ｚ変換という( z は複素数)．
iw )(z ) が
%21: (Z
(Ziw )(z ) =
2
∑az
n =−∞
n −n
+
∞
⎧∞
⎫
⎪
−n ⎪
Z−1 ⎪
⎨∑ yn z ⎪
⎬ (k ) = yk
⎪
⎪
⎪ n =0
⎪z
⎩
⎭
であるからY (z ) の級数表示が分かればよい．
∑b z
n −n
n =−3
2 −2
b − 3z 3
iw )(z ) = a z
+
と表
の と き (Z
1 − a −1z 1 − bz −1
現できるのは b < a のときに限られ，この
ときの {z ; b < z < a } を収束領域という．
%3: 近似解
G
G
Δn x ， An x の片側ｚ変換は
G
∞
G −n
z −1 G
x0
(Δn x )z =
(Z x )(z ) −
∑
h
h
n =0
%41: am ≠ 0 (m > 0) のとき
m
∑ bk z k
k =0
m
∑a z
m
∑b z
k −m
k
=
k
m
k =0
∏(1 − c z )
−1
i
k
i =1
k =0
m
bm
di
+∑
−1
am
i =1 1 − ci z
と部分分数に分解できる( ci ， di は複素数)．
1
−1
%42: (Z Y )(k ) =
Y (z )z k −1dz
v
∫
C
2πi
=
2012-09-30
BAR%0: フーリエ変換
ϕk の集合を完全正規直交系という．
１次元の信号 x : R → R のフーリエ級数とフ
%21: 次式で定められる ϕk の集合， ψk の集合
ーリエ変換について述べる．
はいずれも完全正規直交系である．
1
cos kt
sin kt
， ϕ2k =
， ϕ2k +1 =
2π
π
π
ikt
−ikt
1
e
e
， ψ2k =
， ψ2k +1 =
ψ1 =
2π
2π
2π
ϕ1 =
[1] Wikipedia$フーリエ級数
[2] Wikipedia$フーリエ変換
[3] BAF%ラプラス変換
%1: フーリエ級数
%22: 複素数の信号を扱うときは
任意の t について x (t + 2π) = x (t ) が成立す
る信号 x は次のフーリエ級数 x で近似できる．
x (t ) =
∞
a0
+ ∑ (ak cos kt + bk sin kt )
2
k =1
1 π
x (t )cos kt dt
π ∫−π
1 π
bk = ∫ x (t )sin kt dt
π −π
ak =
[−π, π) 内に有限個の不連続点を含むときは
1
x (t ) = x (t −0) + x (t +0) ．
2
)
%12: 三角関数を指数関数で表現すると
x (t ) =
∞
∑
∫
ck eikt
k =−∞
a
a − ibk
a + ibk
， c−k = k
c0 = 0 ， ck = k
2
2
2
1 π
−ikt
ck =
x (t )e dt
2π ∫−π
%13: 複素数の信号 x : R → C のときも同様
であるが， ck = c−k とは限らない．
π
−π
x (t )y(t )dt
%3: フーリエ変換
y が周期T の周期信号のときは，
1 ∞
⎛ 2π ⎞⎟ i 2Tπ kt 2π
y(t ) =
Y
∑ ⎜ k⎟e T
2π k =−∞ ⎜⎝ T ⎠
⎛ 2π ⎞
Y ⎜⎜ k ⎟⎟ =
⎝T ⎠
%11: 信号 x が連続のときは x = x ． x が区間
(
x, y =
∫
T /2
−T / 2
−i
y(t )e
2π
kt
T
dt
であり，T → ∞ の極限として
y(t ) =
1 ∞
Y (ω)eiωt dω
∫
−∞
2π
Y (ω) = (Fy )(ω) =
∫
∞
−∞
y(t )e−iωt dt
が得られる． Fy を y のフーリエ変換という．
%31: y(t ) ≠ y(t ) となる t の値が多数存在して
も， y − y, y − y = 0 という意味で y =y．
%32: [BAF%14]の δh の h → 0 の極限である超
関数δを用いると， Fδ = {1}ω であり
∞
⎧
⎫
⎪ ∞
ikt ⎪
F⎪
⎨ ∑ ck e ⎪
⎬ (ω) = 2π ∑ ck δ(ω − k )
⎪
⎪
k =−∞
⎪k =−∞
⎪t
⎩
⎭
%2: 正規直交系
%4: 因果性
任 意の t に つい て x (t + a ) = x (t ) (a > 0)
入力の時刻 t における値が出力の時刻 t 以前の
となる a が存在するとき，x を周期信号，この
値に影響しない回路は因果的であるという．
ような a の最小値を x の周期という．周期が
%41: 因果的な回路のインパルス応答は t < 0
2π の信号の空間を考え，信号の内積 x , y を
の領域で 0 であり，そのフーリエ変換の実数部
x, y =
∫
π
−π
x (t )y(t )dt
で定義する．空間内の任意の信号が
ϕk , ϕk = 1 ， ϕi , ϕk = 0 (i ≠ k )
である ϕk (k ∈ N) の１次結合で表せるとき，
と虚数部の一方から他方を計算できる．
%42: [BAF%1]の記号を用いると， (Lx )(iω) =
i
F{x (t )u(t )}t (ω) ． x の両側ラプラス変換 Lx
ix )(α + iω) = F{x (t )e
は (L
−αt
}t (ω) ．
2012-09-30
%31: v の実数部，虚数部，偶関数部，奇関数
BAV%0: ２次元の信号
静止画像は２次元の信号，動画像は３次元の信
号である．主として前者について述べる．
[1] BAR%フーリエ変換
部をそれぞれ Re v ， Im v ， Ev v ， Od v で
表 わ し ， Iv = v ， (Kv )(x , y ) = v(x , y ) ，
⎛x y ⎞
(Mav )(x , y ) = v ⎜⎜⎝ , ⎠⎟⎟ と定めると
a a
I+K
I−K
， Im =
2
2i
I + M−1
I − M−1
Ev =
， Od =
2
2
l = F F ， J = M とおくと
であり， F
Re =
[2] BAF%ラプラス変換
[3] BAK%ｚ変換
%1: 信号の表現
xy -平面上の複素数値の信号 v : R 2 → C を
−1
1 2
考え，簡単のため，標本化周期を単位長に固定
l 2 = J ， (1/ a )F
l M = aM F
l
F
a
1/ a
して標本化した信号にも v を用いる．
l K = KJ F
l =JK F
l
J2 = K2 = I ， F
2
%11: 濃淡画像の場合は v : R → [0, 1] でよ
いが，v のフーリエ変換は複素数値．また，コ
が得られる．したがって，例えば
l Re = F
l
Re F
ヒーレント光学系での v は複素数値の波面．
%32: [BAR%32]の超関数δを用いて定めた
%2: ２次元フーリエ変換
ラプラス変換と関連付けないときは，v のフー
リエ変換V として次式を用いることが多い．
V (μ, ν ) = ∫
∞
−∞
∞
∫
−∞
v(x , y )e−i2 π(μx +νy )dx dy
[BAF%1]と同様に，一般には通用しない便宜的
な記法 v = {v(x , y )}x ,y を用い，
∫
(F v )(x , ν ) = ∫
(F1v )(μ, y ) =
2
∞
−∞
∞
−∞
v(x , y )e−i2 πμx dx
v(x , y )e−i2 πνy dy
と定めると( Fk は k 番目の変数に対する変換)，
V = F1F2v = F2 F1v である．詳しくかくと
(F1F2v )(μ, ν ) = F1 {(F2v )(x , ν )}x ,ν (μ, ν ) ．
comb(x ) =
定義の類似性から，[BAF%2]と同様の公式が得
られる．例えば
F1F2 {v(x −a, y −b)}x ,y (μ , ν )
= e−i2 π(a μ+bν )(F1F2v )(μ, ν )
が成立する．また， F
n
k k
= F F とかくと
(F12 F22v )(x , y ) = v(−x , −y )
4
したがって (F1F2 ) v = v ．
∞
∑ δ(x − k )
k =−∞
は F1 comb = comb を満足する(標本化定理
の説明に便利であるが証明は難しい)．また
F1 {Φ(2 x ≤ 1)}x (μ) = sin(πμ)/ πμ
F1 {exp(−πx 2 )}x (μ) = exp(−πμ2 )
%4: 離散フーリエ変換
v が周期的な信号で
v(x + N 1, y + N 2 ) = v(x , y )
のときは，[BAR%3]と同様に近似式
v(x , y ) =
N 1 −1 N 2 −1
∑ ∑ V ( j, k ) e
⎛ jx ky ⎞
i2 π⎜⎜⎜ + ⎟⎟⎟
⎜⎝ N 1 N 2 ⎠⎟
j =0 k =0
%3: 公式
n +1
k
I+K+JK+J l
= F Ev Re
4
V ( j, k ) =
⎛ jx ky ⎞
−i2 π⎜⎜⎜ + ⎟⎟⎟
⎜⎝ N 1 N 2 ⎠⎟
N 1 −1 N 2 −1
∑ ∑ v(x, y)e
j =0 k =0
を考え，V を v の離散フーリエ変換という．
%41: v の繰返し部分の２次元ｚ変換は
v )(z , z ) =
(Z
1
2
N 1 −1 N 2 −1
∑ ∑ v(x, y )z
− j −k
1
2
z
j =0 k =−∞
v )(e
であり，V ( j, k ) は (Z
i2 πμ
, ei2 πν ) の (μ, ν )
= ( j / N 1, k / N 2 ) における値に等しい．
2012-06-17
C6D%0: 巡回符号の復号
E (x ) = x i E 0 (x ) ，Γx −4E 0 (x ) = 0 ，E 0 (0) = 1
巡回符号の復号の考え方を説明する（多項式を
の場合（バースト誤り）のシンドローム S (x )
降べきの順で扱う等，慣用の表現と異なる）．
= G (x )Δ{E (x )/G (x )} について考える．
[1] Wikipedia$誤り検出訂正
Δ
[2] Wikipedia$復号手法
∞
⎪⎧⎪ i−7
⎪⎫
z −7S (z )
=
Δ
z
E
(
z
)
z −7 j ⎪⎬
⎨
∑
0
−7
7
⎪⎩⎪
⎪⎭⎪
z (z + 1)
j =0
[3] Wikipedia$巡回符号
であるから，左辺も級数に展開することで
[4] Wikipedia$BCH符号
i1 = 7Δ(i / 7) と E 0 (z ) が分かる．一方
[5] Wikipedia$リード・ソロモン符号
%1: 線形の２元ブロック符号
n
S (z )
z i E 0 (z )
Δ 4
=Δ 4
z +z +1
z +z +1
１次独立な h1, ", hm (hi ∈ {0, 1} ) と直交
が成立し，%2 と同様の計算で上式を満足する
するベクトルを符号語にすると伝送誤りの検
i2 = 15Δ(i /15) が分かる．したがって符号語
出が容易で，工夫により簡単な誤り訂正も可能．
長が 7 × 15 以下であれば i1 ，i2 から（例えば中
3
%11: [#46]でG (x ) = x + x + 1 の場合，
⎛1 1 1 0 1 0 0⎞⎟
⎜⎜
⎟⎟
⎜
T
H = ⎜⎜0 1 1 1 0 1 0⎟⎟⎟
⎜⎜
⎟
⎜⎜1 1 0 1 0 0 1⎟⎟⎟
⎝
⎠
国の剰余定理を用いて） i の値が得られる．
4
%31: x + x + 1 は原始多項式である[#42]．
%4: 簡単なBCH符号
%2 の拡張として M ′(α) = 0 ，M ′′(α ) = 0 で
3
に対して H v = 0 となる v が符号語．
ある多項式の積 G (x ) = M ′(x )M ′′(x ) を生成
%2: 巡回ハミング符号
多項式とする符号を考える（ M ′(α ) = 0 ）．
T
2
[#46]のY (x ) は G (α) = 0 である α に対して
M ′(x ) = x 4 + x + 1
Y (α) = 0 となる多項式である．単一誤りを仮
M ′′(x ) = x 4 + x 3 + x 2 + x + 1
i
定して Ri (x ) = G (x )Δ{x /G (x )} とおくと，
Ri (x ) について次の漸化式が成立する．
⎫
⎪⎧ x
xi ⎪
⎪
Ri +1(x ) = G (x )Δ ⎪⎨
G (x )Δ
⎬
⎪⎪⎩G (x )
G (x )⎪⎪
⎭
xRi (x )
= xRi (x ) − G (x )Γ
G (x )
の場合 α
15
= 1 である．
S ′(x ) = M ′(x )Δ{E (x )/ M ′(x )}
S ′′(x ) = M ′′(x )Δ{E (x )/ M ′′(x )}
i
対して S ′(α) = α + α ，S ′′(α ) = α + α
i
i
Γ{Ri (x )/ x 2 } = 0 ならば Ri +1(x ) = xRi (x ) ，そ
うでなければ Ri +1(x ) = xRi (x ) −G (x ) である．
%21: シンドロームと等しい Ri (x ) は特定でき
j
3i
3
j
%41: M ′′(α ) = 0 であるが S ′′(x ) は多項式で，
3
Ri′′(x ) = M ′′(x )Δ
xi
は R5′′(x ) = R0′′(x ) ．
M ′′(x )
%42: %11 に対応する (8, 15) 行列 H は
%3: ファイア符号
⎛α14
⎜
H = ⎜⎜ 12
⎜⎜α
⎝
7
4
ある巡回符号について，伝送誤りの多項式が
3j
となる α ， α を計算できる．
るが， E (x ) が単一誤りか否かは検証不能．
生成多項式がG (x ) = (x + 1)(x + x + 1) で
j
とおくと，伝送誤りの多項式 E (x ) = x + x に
T
T
α 0 ⎞⎟
⎟⎟
α 0 ⎠⎟⎟
α13 " α10 " α1
α9
" α0
" α3
で，単一誤りのときは S ′(α) = S ′′(α ) ．
3
3
2012-07-15
C74%0: ハール・ウェーブレット
レット変換の場合， a ， b は離散値で，%2 の
もっとも基本的なウェーブレットであるハー
ψ(t ) は次の ψ(t ) の M = 1 の場合に相当．
2M −1
ϕ(t ) = ∑ αj 2ϕ(2t − j )
ル･ウェーブレットについて説明する．
j =0
[1] Wikipedia$ウェーブレット
ψ(t ) =
[2] Wikipedia$離散ウェーブレット変換
2M −1
∑ (−1) α
j
2ϕ(2t − j )
2M − j −1
j =0
%1: 関数の階段近似
%3: 多重解像度解析
命題 X が真のとき 1 ，偽のとき 0 となる X の
標本化された入力信号を想定し，標本値 x (k )
関数を Φ(X ) で表わす．ϕ(t ) = Φ(0 ≤ t < 1) は
= c0,k から cn ,k ， dn ,k を次式で計算する．
ϕ(t ) = ϕ(2t ) + ϕ(2t − 1) を満足する．ϕn ,k (t ) を
ϕn ,k (t ) = 2−n / 2 ϕ (2−n t − k )
で定めると， x , ϕn ,k =
∫
∞
−∞
x (t ) ϕn ,k (t )dt を
用いて， x (t ) を次のように近似できる．
x n (t ) =
∞
∑
x , ϕn ,k ϕn ,k (t )
Dn = (dn ,0 , ", dn ,ν (N −n )−1 ) (ν(k ) = 2k )
が得られ， c0,k はこれから逆算できる．
%2: ウェーブレット変換
δi, j = Φ(i = j ) とする． ϕn,k , ϕn ,A = δk ,A で
ある．yn (t ) = x n −1(t ) − x n (t ) とおき，ψn ,k (t ) を
ψn ,k (t ) = 2
N
これにより x 0 (t ) (0 ≤ t < 2 ) の分析結果
(D1, D2, ", DN , cN , 0 )
k =−∞
−n / 2
⎛1 1 ⎞⎟ ⎛ cn −1,2k ⎞
⎛cn ,k ⎞⎟
⎜⎜ ⎟ = 1 ⎜⎜
⎟⎟⎜⎜
⎟⎟⎟
⎜
⎜⎝⎜dn ,k ⎠⎟⎟
c
⎟
⎜
1
1
−
2 ⎝⎜
⎠⎟ ⎝ n −1,2k +1 ⎠⎟
c0,0 c0,1 c0,2 c0,3 c0,4 c0,5 c0,6 c0,7
d1,0
d1,1
d1,2
d2,0
d2,1
ψ (2 t − k )
d3,0
−n
c3,0
ψ(t ) = ϕ (2t ) − ϕ(2t − 1)
dn ,k は dn −1,A に比べて，時間分解能が半分，周
で定めると， ϕn ,k , ψn ,A = 0 であり，
yn (t ) =
∞
∑d
n ,k
波数分解能が２倍である．
ψn,k (t )
%41: 因果的な回路での計算を考慮して
k =−∞
∞
∫ y(t ) ψ
x (t ) = ∑ y (t ) = ∑ ∑ d
dn ,k = y, ψn ,k =
∞
−∞
∞
∞
n
0
n =1
n ,k
n ,k
(t )dt
C n (z ν (n ) ) =
ψn ,k (t )
Dn (z ν (n ) ) =
n =1 k =−∞
∑c
n ,k
z −(k +1)ν (n )
k =−∞
∞
∑d
n ,k
z −(k +1)ν (n )
とおく．これらは信号C n −1(z
が成立する．ϕ(t ) をスケーリング関数，ψ(t ) を
ウェーブレット関数という．
%21: ウェーブレット関数 ψ(t ) を用いた変換
⎛t − b ⎞
∫−∞ x (t )ψ ⎜⎜⎝ a ⎠⎟⎟⎟ dt
∞
−iat
の積
分で窓 w(t − b) は伸縮しない．離散ウェーブ
ν (n −1)
) を伝達関数
⎛H (z ν (n −1) )⎞⎟
−ν (n −1) ⎛1
1 ⎞⎟ ⎜⎛ 1 ⎞⎟
⎜⎜
⎟⎟ = z
⎟
⎜⎜⎜
⎟⎜
⎜⎜1 −1⎟⎟⎟ ⎜⎜z −ν (n −1) ⎟⎟⎟
⎜⎜G (z ν (n −1) )⎟⎟⎟
2
⎜
⎝
⎠⎝
⎠
⎝
⎠
のフィルタを通して間引いた信号に等しい．
%42: 信 号 Y (z ) =
をウェーブレット変換という（ ψ は複素共役）．
窓付きフーリエ変換は x (t )w(t − b)e
∞
k =−∞
ψn,k (t ), ψm ,A (t ) = δn,m δk ,A
1
(Tx )(a, b) =
a
d1,3
∞
∑ (y
2k
+ y2k +1z −1 ) z −2k に
k =0
Y (z ) + Y (−z )
で，
2
Y (e i(ω +π ) ) −Y (e iω )
．
折り返し雑音は
2
y2k +1 = 0 を代入した信号は
2012-09-30
C7S%0: デルタ関数
微分可能なふつうの関数のとき
∞
v ′, ϕ = [v(t )ϕ(t )]−∞ − ∫
∞
−∞
一般には通用しない[BAF%]，[BAR%]の記号も用
v(t )ϕ ′(t )dt
いてデルタ関数の定義・性質を述べる．
で，右辺第１項は 0 に等しいので，v が超関数
[1] Wikipedia$ディラックのデルタ関数
のときも w, ϕ = − v, ϕ ′ となる w を v の
[2] Yoshino$超関数論
導関数 v ′ と考える．したがって不連続な関数
[3] ShinoMatsuMatsu$デルタ関数入門
も微分できる．高階の導関数は
[4] BAF%ラプラス変換
v (n ), ϕ = (−1)n v, ϕ(n )
sin λt
%31: δ(−t ) = δ(t ) ， lim
= δ(t ) ．
λ →∞
πt
[5] BAR%フーリエ変換
%1: 定義
%32: u ′ = δ ， δ , ϕ = (−1) ϕ (0) ．
(n )
δ(t ) = 0 (t ≠ 0) で，任意の ϕ(t ) について
∫
∞
−∞
δ(t )ϕ(t )dt = ϕ(0)
となる δ(t ) を(１変数の)ディラックのデルタ
関数という． δ(t ) は普通の関数ではないので，
シュヴァルツの超関数あるいは佐藤の超関数
として扱わねばならない．
n
(n )
%4: フーリエ変換
(試験関数を急減少関数，v を緩増加超関数と
して) v のフーリエ変換を Fv で表わすと，
(Fδ)(ω) = 1 ， (F−1 {1}ω )(t ) = δ(t )
1
(Fu)(ω) =
+ πδ(ω)
iω
%2: シュヴァルツの超関数
ま た w, ϕ = v1, v2 ∗ ϕ の と き w = v1 ∗ v2
集合 {t ; ϕ(t ) ≠ 0} の閉包を ϕ(t ) の台といい，
と考えると， (Fv ′)(ω) = iω(Fv )(ω ) であり，
台が有界で無限回微分可能な関数を試験関数
F(v1 ∗ v2 )(ω) = (Fv1 )(ω) (Fv2 )(ω)
という．また，一般化された関数 v と試験関数
(v1 ∗ v2 )′ = v1′∗ v2 = v1 ∗ v2′
%6: 佐藤の超関数
ϕ の内積を
v, ϕ =
∫
∞
−∞
v(t )ϕ(t )dt
で表し，任意の ϕ について v, ϕ = w, ϕ で
あれば超関数として v = w であると考える．
%21: 試験関数の例は
⎛
1 ⎞⎟
ϕ(t ) = exp ⎜⎜−
Φ( t < 1)
⎝ 1 − t 2 ⎠⎟
実関数 v の値 v(t ) を複素関数V (z ) の上半平面
上からの境界値V (t + i0) と下半平面上からの
境界値V (t − i0) の差と考える．
%61: U (z ) = −
)
1
log(−z )
2π i
( −π < arg z ≤
π とおくと U (t + i0) −U (t − i0) = Φ(t > 0)
%22: v(t ) = Φ(t ∈ Z) は v, ϕ = 0 となるの
1
+ Φ(t = 0) であり，U ′(z ) は δ(t ) に対応．
2
で，超関数として考えると v = 0 ．
%7: 多変数のデルタ関数
%23: v を ϕ (急減少関数に拡張できる) が属
する線形空間上の線形汎関数として扱う．
%3: 極限と導関数
lim vn , ϕ = v, ϕ のとき vn は v に(弱)収
G
G
G G
G
δ(r ) = 0 (r ≠ 0) ， δ, ϕ = ϕ(0) となる δ(r )
G
3
はシュヴァルツの超関数で， r ∈ R のとき
G
1
∇2
G = δ(r ) = δ(x )δ(y )δ(z ) ．
4π r
n →∞
束するという．lim v ε , ϕ も同様．また，v が
ε→ 0
%71: 多変数の佐藤の超関数は極めて難解．
© Copyright 2024 ExpyDoc
