補遺 - OCN

http//pulsar.blog.ocn.ne.jp/bonsai/sys-s.pdf------------------------------------------------------------2012.08
Supplements to Integrated Examples on
Discrete Systems
[email protected]---------------------------------------©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%]z変換,[BAR%]
フーリエ変換,[BAV%]2次元の信号,[C74%]
ハール・ウェーブレット,[C7S%]デルタ関数,
#84: 巡回符号
[1#未%]ルベーグ積分,[1#B91%]初等関数,
2011-10-12
B6F%0: いろいろな空間
E n の点は a1e1 + " + anen ,2点 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次元
3
のユークリッド空間 E である.例えば,地上
(1) (x, x ) ≥ 0 ,かつ x = 0 ⇔ (x, x ) = 0
(2) (x, y ) = (y, x ) ( (y, x ) の共役複素数)
の1点 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 内の2点 (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 ∈ Ω) の2次
%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: 任意の2節点間に経路が存在するグラフ
%4: その他
を連結グラフという(枝の向きに従った経路の
以下は sys.pdf の参照番号・内容未定のため後
場合は「強連結」ということが多い).
日追加します.
%2: 木
・状態遷移図
V を人間の集合, (v1, v2 ) ∈ E を「 v1 は v2 の
・シグナルフロー・グラフ
親である」としてグラフを描くことができる.
法律的でなく生物学的な親子関係で考えれば,
このグラフには閉路は存在しない.閉路のない
連結グラフを木という.
%21: (v1, v2 ) ∈ E が「 v1 は v2 の親である」を
2011-08-15
B72%0: 離散情報の符号化
(− log2 qi ) の2値系列に符号化できれば,平均
シャノンの情報理論の主要部分である情報源
符号語長は情報源のエントロピーをビットで
符号化と通信路符号化について説明する.
表わした値のほぼ 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 値の系列に符号化するとき,情報源1記号
きいというだけでなく,自然な性質
当たりの長さを 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 の系
路で1秒当たりに伝送できる情報量の最大値
列を送る場合を考え,S 3 = {a1, a2 , a 3 } ,S 2 =
C (通信路容量)は,
{0, 1} とおく.1対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 を長さがほぼ
度は1秒当たりに伝送する情報量である.
%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: z変換
差分方程式をz変換すると代数方程式になる.
であるから,%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: 双1次変換
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 ) で はz 変換 を使
るから,x ′′(t ) + ω x (t ) = 0 を%1 のように離
G
G
G
G
2
えないのでGn +1/ 2 , v n +1/ 2 を用いる方がよい.
散近似した解も振幅は一定である(4次の陽的
%2: 両側z変換
ルンゲクッタ法の近似解は発散する).
Gi
Gi
[#33]の片側z変換 Z を [Zx ]1 = Z[x ]1 と拡張し, %4: 逆z変換
(Zy )(z ) = Y (z ) で あ る y を Y = {Y (z )}z の
同様に定義される
G
(Zi x )(z ) =
∞
G
∑x
n
−1
z −n
逆z変換といい, Z Y で表わす(BAF%1).
n =−∞
を両側z変換という( 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 の片側z変換は
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 の集合を完全正規直交系という.
1次元の信号 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) の1次結合で表せるとき,
と虚数部の一方から他方を計算できる.
%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: 2次元の信号
静止画像は2次元の信号,動画像は3次元の信
号である.主として前者について述べる.
[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%z変換
%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: 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 の繰返し部分の2次元z変換は
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: 線形の2元ブロック符号
n
S (z )
z i E 0 (z )
Δ 4
=Δ 4
z +z +1
z +z +1
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
波数分解能が2倍である.
ψ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
いてデルタ関数の定義・性質を述べる.
で,右辺第1項は 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 ) を(1変数の)ディラックのデルタ
関数という. δ(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: 多変数の佐藤の超関数は極めて難解.