情報科学基礎講義 ノート4 情報科学基礎講義 ノート4

情報科学基礎講義
情報科学基礎講義
ノート４
ノート４
平成20年1月７日
平成20年1月７日
今瀬
今瀬 真
真
講義ノート
講義ノート pp.63-86
pp.63-86
http://www.ispl.jp/~imase/lecture/isbasic/2007
１０.
１０. CASL
CASL IIプログラミング（ビット操作）
IIプログラミング（ビット操作）
10.1
10.1 論理演算とシフト演算
論理演算とシフト演算
•• 論理演算：1語のデータは16ビットで構成される
論理演算：1語のデータは16ビットで構成される 。各
。各
ビットごとに独立した演算
ビットごとに独立した演算
–– 論理積(AND)、論理和(OR)、排他的論理和(XOR)
論理積(AND)、論理和(OR)、排他的論理和(XOR)
Ｘ
Ｙ
論理積
論理和
０
０
１
１
０
１
０
１
０
０
０
１
０
１
１
１
排他的
論理和
０
１
１
０
1
AND
AND GR0,GR1
GR0,GR1 (100ページ)
(100ページ)
•• レジスタ間の論理積
レジスタ間の論理積
内容
ＧＲ０
1000000000000001
=(8001)16
ＧＲ１
0011010100100001
=(3521)16
命令実行
ＧＲ０
0000000000000001
=(0001)16
ＧＲ１
0011010100100001
=(3521)16
FR
OF SF ZF
0 0 0
OR
OR GR0,GR1
GR0,GR1 (104ページ)
(104ページ)
•• レジスタ間の論理和
レジスタ間の論理和
内容
ＧＲ０
1000000000000001
=(8001)16
ＧＲ１
0011010100100001
=(3521)16
命令実行
ＧＲ０
1011010100100001
=(B521)16
ＧＲ１
0011010100100001
=(3521)16
FR
OF SF ZF
0 1 0
2
XOR
XOR GR0,GR1
GR0,GR1 (106ページ)
(106ページ)
•• レジスタ間の排他的論理和
レジスタ間の排他的論理和
内容
ＧＲ０
1000000000000001
=(8001)16
ＧＲ１
0011010100100001
=(3521)16
命令実行
ＧＲ０
1011010100100000
=(B520)16
ＧＲ１
0011010100100001
=(3521)16
FR
OF SF ZF
0 1 0
AND
AND GR0,A
GR0,A (101ページ)
(101ページ)
•• レジスタとメモリの論理積
レジスタとメモリの論理積
内容
ＧＲ０
0011010001000100
=(3444)16
Ａ番地
0000000011011101
=(00DD)16
命令実行
ＧＲ０
0000000001000101
=(0001)16
Ａ番地
0000000011011101
=(00DD)16
FR
OF SF ZF
0 0 0
3
OR
OR GR0,A
GR0,A (105ページ)
(105ページ)
•• レジスタとメモリの論理和
レジスタとメモリの論理和
内容
ＧＲ０
0011010001000100
=(3444)16
Ａ番地
0000000011011101
=(00DD)16
命令実行
ＧＲ０
0011010011011101
=(34DD)16
Ａ番地
0000000011011101
=(00DD)16
FR
OF SF ZF
0 0 0
XOR
XOR GR0,A
GR0,A (107ページ)
(107ページ)
•• レジスタとメモリの排他的論理和
レジスタとメモリの排他的論理和
内容
ＧＲ０
0011010001000100
=(3444)16
Ａ番地
0000000011011101
=(00DD)16
命令実行
ＧＲ０
0011010010011001
=(3499)16
Ａ番地
0000000011011101
=(00DD)16
FR
OF SF ZF
0 0 0
4
応用:汎用レジスタの特定ビットを取り出
応用:汎用レジスタの特定ビットを取り出
す(101ページ)
す(101ページ)
•• AND
AND GR0,A
GR0,A
内容
ＧＲ０
0011010001000100
=(3444)16
Ａ番地
1111111100000000
=(FF00)16
命令実行
上位8ビットの取り出し
ＧＲ０
0011010000000000
=(3400)16
Ａ番地
0000000011011101
=(00DD)16
FR
OF SF ZF
0 0 0
応用:汎用レジスタの偶奇の判定(102ページ)
応用:汎用レジスタの偶奇の判定(102ページ)
EVEN
EVEN
ODD
ODD
AND
;(A=(0001)
AND GR0,A
GR0,A
;(A=(0001)1616））
JNZ
JNZ ODD
ODD
（偶数の処理）
（偶数の処理）
(奇数の処理）
(奇数の処理）
内容
ＧＲ０
0011010001000100
=(3444)16
Ａ番地
0000000000000001
=(0001)16
AND
GR0,A 命令実行
ＧＲ０
0000000000000000
=(3400)16
Ａ番地
0000000011011101
=(00DD)16
FR
OF SF ZF
0 0 1
5
応用:ビットの反転(107ページ)
応用:ビットの反転(107ページ)
•• XOR
XOR GR0,A
GR0,A
；(A=
；(A= (FFFF)
(FFFF)1616））
内容
ＧＲ０
0001001000010110
=(1216)16
Ａ番地
1111111111111111
=(FFFF)16
命令実行
上位8ビットの取り出し
ＧＲ０
1110110111101001
=(EDE9)16
Ａ番地
1111111111111111
=(00DD)16
FR
OF SF ZF
0 1 0
応用:2の補数の求め方(108ページ)
応用:2の補数の求め方(108ページ)
••
••
XOR
XOR GR0,A
GR0,A
ADDA
ADDA GR0,C1
GR0,C1
；(A=
；(A= (FFFF)
(FFFF)1616））
;; (C1=
(0001)1616））
(C1= (0001)
ＧＲ０
0000000000000101
=(0005)16
Ａ番地
1111111111111111
=(FFFF)16
C1番地 0000000000000001
=(0001)16
XOR GR0,A命令実行(ビットの反転）
ＧＲ０
1111111111111010
ADDA GR0,C1命令実行(１加算）
ＧＲ０
1111111111111011
=(FFFB)16 =(-5)10
6
応用:内容の一致のチェック(108ページ)
応用:内容の一致のチェック(108ページ)
XOR
XOR GR0,A
GR0,A
JNZ
L2
JNZ
L2
（一致した場合の処理）
（一致した場合の処理）
(一致しなかった場合の処理）
(一致しなかった場合の処理）
L1
L1
L2
L2
内容
ＧＲ０
0011010001000100
=(3444)16
Ａ番地
0011010001000100
=(3444)16
XOR
GR0,A 命令実行
ＧＲ０
0000000000000000
=(0000)16
Ａ番地
0011010001000100
=(3444)16
FR
OF SF ZF
0 0 1
（２）
（２） シフト命令
シフト命令
••
••
••
16ビット列を左あるいは右に指定されたビット数だけずらす．
16ビット列を左あるいは右に指定されたビット数だけずらす．
4種類のシフト演算命令
4種類のシフト演算命令
符号ビットを意識する(符号ビットだけは元のままにする)の
符号ビットを意識する(符号ビットだけは元のままにする)の
が算術演算で，そうでないのが論理演算である．
が算術演算で，そうでないのが論理演算である．
–– 左論理シフト(SLL)、右論理シフト(SRL)
左論理シフト(SLL)、右論理シフト(SRL)
–– 左算術シフト(SLA)、右算術シフト(SRA)
左算術シフト(SLA)、右算術シフト(SRA)
ｎ
•• nビットの左算術シフトは、２の補数表現で２
nビットの左算術シフトは、２の補数表現で２ｎ倍
倍
ｎ
•• nビットの右算術シフトは、２の補数表現で1/2
倍の効果がある。
nビットの右算術シフトは、２の補数表現で1/2ｎ倍の効果がある。
•• シフト演算の結果に応じて(符号付の数とみて)フラグレジス
シフト演算の結果に応じて(符号付の数とみて)フラグレジス
タFRに正(000)，零(001)，負(010)が設定される．
タFRに正(000)，零(001)，負(010)が設定される．
7
SLA
SLA GR0,2
GR0,2
;(110ページ)
;(110ページ)
•• レジスタの内容の算術左シフト
レジスタの内容の算術左シフト
内容
消失
ＧＲ０
0011000101110101
=(3175)16
命令実行
ＧＲ０
消失したビットに
１が含まれると
オーバフロー
最上位ビッが
０（正）の時
0100010111010100
FR
OF SF ZF
1 0 0
SLA
SLA GR0,1,GR1
GR0,1,GR1
=(45D4)16
０が埋め込まれる
最上位ビットが１の時：
消失したビットに０が含まれると
アンダーフロー
;(110ページ)
;(110ページ)
•• レジスタの内容の算術左シフト
レジスタの内容の算術左シフト
ＧＲ1
0000000000000010
=(0002)16
ＧＲ0
1001101000111110
=(9A3E)16
命令実行
3bitシフト（=1+GR1)
ＧＲ０
1101000111110000
=(D1F0)16
FR
OF SF ZF
1 1 0
8
SRA
SRA GR0,2
GR0,2
;(113ページ)
;(113ページ)
•• レジスタの内容の算術右シフト
レジスタの内容の算術右シフト
内容
消失
ＧＲ０
0111101000110001
=(7A31)16
命令実行
ＧＲ０
0001111010001100
符号が埋め込まれる
最後に送り出された
値がＯＦに設定される
SRA
SRA GR0,1,GR1
GR0,1,GR1
=(1E8C)16
FR
OF SF ZF
0 0 0
;(114ページ)
;(114ページ)
•• レジスタの内容の算術右シフト
レジスタの内容の算術右シフト
ＧＲ1
0000000000000010
=(0002)16
ＧＲ0
1010001000111000
=(A238)16
命令実行
3bitシフト（=1+GR1)
ＧＲ０
1111010001000111
符号が埋め込まれる
=(F447)16
FR
OF SF ZF
1 1 0
9
シフト命令と乗算
シフト命令と乗算
••
••
ｎ
nビットの左算術シフトは、２の補数表現で2
nビットの左算術シフトは、２の補数表現で2ｎ倍
倍
ｎ
nビットの右算術シフトは、２の補数表現で1/2
nビットの右算術シフトは、２の補数表現で1/2ｎ倍の効果が
倍の効果が
ある。
ある。
0000000000000110 =(6)10
1111111111111110 =(-2)10
1ビット左シフトは２倍
0000000000001100 =(12)10 1111111111111100 =(-4)10
1ビット右シフトは1/2倍
0000000000000011 =(3)10 1111111111111111 =(-1)10
2の補数の乗算（AとB=(b15,b14,b13,….b2,b1,b0))
A×B
= A*b0*1+A*b1*2+A*b2*22 +…+A*b13*213 + A*b14*214 - A*b15*215
SLL
SLL GR0,2
GR0,2
;(120ページ)
;(120ページ)
•• レジスタの内容の算術左シフト
レジスタの内容の算術左シフト
内容
消失
ＧＲ０
0111100100110101
=(7935)16
命令実行
最後に送り出された
ビットがオーバフ
ローにセットされる
ＧＲ０
1110010011010100
FR
OF SF ZF
1 1 0
=(45D4)16
0が埋め込まれる
10
SLL
SLL GR0,1,GR1
GR0,1,GR1
;(120ページ)
;(120ページ)
•• レジスタの内容の算術左シフト
レジスタの内容の算術左シフト
ＧＲ1
0000000000000010
=(0002)16
ＧＲ0
1000101111001111
=(8BCF)16
命令実行
3bitシフト（=1+GR1)
ＧＲ０
0101111001111000
=(D1F0)16
FR
OF SF ZF
1 0 0
SRL
SRL GR0,2
GR0,2
;(121ページ)
;(121ページ)
•• レジスタの内容の算術右シフト
レジスタの内容の算術右シフト
内容
消失
ＧＲ０
0011010110101101
=(35AD)16
命令実行
ＧＲ０
0000110101101011
0が埋め込まれる
最後に送り出された
値がＯＦに設定される
=(1E8C)16
FR
OF SF ZF
0 0 0
11
SRL
SRL GR0,1,GR1
GR0,1,GR1
;(121ページ)
;(121ページ)
•• レジスタの内容の算術右シフト
レジスタの内容の算術右シフト
ＧＲ1
0000000000000010
=(0002)16
ＧＲ0
1011011110101100
=(B7AC)16
命令実行
3bitシフト（=1+GR1)
ＧＲ０
0001011011110101
0が埋め込まれる
=(16F5)16
FR
OF SF ZF
1 1 0
10.2
10.2 座席予約システム
座席予約システム
•• ビット操作の1つの応用として単純化した座席予約システム
ビット操作の1つの応用として単純化した座席予約システム
の開発を行う．
の開発を行う．
•• 対象となる乗り物には2人掛けを基本とした8席がある．
対象となる乗り物には2人掛けを基本とした8席がある．
•• 要求があれば2人掛けの席を2つの席に分けて使用することも
要求があれば2人掛けの席を2つの席に分けて使用することも
許す.
許す.
•• 座席予約システムの開発にあたって16ビットの状態ベクトル
座席予約システムの開発にあたって16ビットの状態ベクトル
(RES)を導入する．
(RES)を導入する．
座席
番号
座席番号
RES
0
1
0
1
2
3
2
3
4
5
4
6
7
5
6
8 10 12 14
9 11 13 15
7
8
9 10 11 12 13 14 15
0 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0
0は空席、1は予約済みを示す.
12
座席予約システムの開発項目
座席予約システムの開発項目
座席予約システムの基本機能として次の4つの開発を
座席予約システムの基本機能として次の4つの開発を
目指す。
目指す。
1.
1. 空席の有無の確認：RESがすべて1かどうかの
空席の有無の確認：RESがすべて1かどうかの
チェック
チェック
2.
2. ２人掛けの予約：0,2,4,…,14から始まる00(または
２人掛けの予約：0,2,4,…,14から始まる00(または
11)のチェック
11)のチェック
3.
3. 予約数の確認：RES中の1の総数の計算
予約数の確認：RES中の1の総数の計算
4.
4. 座席番号の確認：2分探索木の構成
座席番号の確認：2分探索木の構成
0
座席番号
RES
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15
0 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0
10.3
10.3 空席の有無の確認
空席の有無の確認
•• RESのすべてのビットが1になっているか
RESのすべてのビットが1になっているか
PRG407
VACANT
FULL
RES
ALLONE
START
LD
CPL
JZE
…
…
…
…
RET
DS
DC
…
END
GR0,RES
GR0,ALLONE
FULL
；空席あり
；空席なし
RES=1111 1111 1111 1111
のときだけFR001(零)
が設定され,FULLに分
岐する.
1
#FFFF
13
10.4
10.4 2人掛けの席の予約
2人掛けの席の予約
(1)
(1) 座席0,
座席0, 1が空席かどうかのチェック
1が空席かどうかのチェック
方針：CPLとJZEの組み合わせ
方針：CPLとJZEの組み合わせ
でこの機能を実現する
でこの機能を実現する
•• 予約状況(RES)の0と1を反
予約状況(RES)の0と1を反
転させて，1が空席を表す
転させて，1が空席を表す
ようにして，
ようにして，
•• 上位2ビットを取り出して
上位2ビットを取り出して
•• PAIR:1100
PAIR:1100 0000
0000 0000
0000 0000
0000
との間で論理比較をすれば
との間で論理比較をすれば
よい。
よい。
PRG408
START
LD
XOR
AND
CPL
JZE
NOK
…
…
OK
…
…
RET
RES
DS
ALLONE DC
PAIR
DC
…
END
GR0,RES
GR0,ALLONE
GR0,PAIR
GR0,PAIR
OK
；空席でない
；空席
1
#FFFF
#C000
10.4
10.4 2人掛けの席の予約
2人掛けの席の予約
(1)
(1) 座席0,
座席0, 1が空席かどうかのチェック
1が空席かどうかのチェック
START
LD
XOR
AND
CPL
JZE
NOK
…
…
OK
…
…
RET
RES
DS
ALLONE DC
PAIR
DC
…
END
例1
PRG408
GR0,RES
GR0,ALLONE
GR0,PAIR
GR0,PAIR
OK
；空席でない
；空席
1
#FFFF
#C000
GR0←0010 0011 0011 0000
GR0←1101 1100 1100 1111
GR0←1100 0000 0000 0000
FR
OF SF ZF
0 0 1
RES=0010 0011 0011 0000
14
10.4
10.4 2人掛けの席の予約
2人掛けの席の予約
(1)
(1) 座席0,
座席0, 1が空席かどうかのチェック
1が空席かどうかのチェック
START
LD
XOR
AND
CPL
JZE
NOK
…
…
OK
…
…
RET
RES
DS
ALLONE DC
PAIR
DC
…
END
例2
PRG408
GR0,RES
GR0,ALLONE
GR0,PAIR
GR0,PAIR
OK
；空席でない
GR0←1010 0011 0011 0000
GR0←0101 1100 1100 1111
GR0←0100 0000 0000 0000
FR
OF SF ZF
0 1 0
；空席
RES=1010 0011 0011 0000
1
#FFFF
#C000
10.4
10.4 2人掛けの席の予約
2人掛けの席の予約
(1)前方の2人掛けの席の予約
(1)前方の2人掛けの席の予約
方針：2人掛けの空席を前方か
方針：2人掛けの空席を前方か
ら調べていって，見つかる
ら調べていって，見つかる
とそこに予約を入れること
とそこに予約を入れること
を考える．
を考える．
•• 前述の座席0,
前述の座席0, 1の空きの
1の空きの
チェックを利用する
チェックを利用する
•• そのために論理右シフト
そのために論理右シフト
(SRL
(SRL GR1,2)を利用して8種
GR1,2)を利用して8種
類のパターンを順次生成
類のパターンを順次生成
––
––
––
––
GR1=1100
GR1=1100 0000
0000 0000
0000 0000
0000
GR1=
0011
0000
GR1= 0011 0000 0000
0000 0000
0000
………
………
GR1=
GR1= 0000
0000 0000
0000 0000
0000 0011
0011
•• 空いていることが判明した
空いていることが判明した
ら，論理和により11を設定
ら，論理和により11を設定
PRG408
LOOP
NOK
OK
START
LD
XOR
LD
LD
AND
CPL
JZE
SRL
JNZ
…
LD
OR
ST
…
RET
…
END
GR0,RES
GR0,ALLONE
GR1,PAIR
GR2,GR0
GR2,GR1
GR2,GR1
FULL
GR1,2
OK
；空席なし
GR0,RES；空席
GR0,GR1
GR0,RES
15
10.5
10.5 予約数の確認
予約数の確認
予約数を求めるにはRES中に含まれる1の総数を計算す
予約数を求めるにはRES中に含まれる1の総数を計算す
ればよい．
ればよい．
(1)自然な方法
(1)自然な方法
1.
1. GR0の内容(RESの内容そのもの)を1ビットずつ右
GR0の内容(RESの内容そのもの)を1ビットずつ右
へシフトしながら，
へシフトしながら，
2.
2. その時点でのGR0の右端の1ビットが1かどうか調
その時点でのGR0の右端の1ビットが1かどうか調
べる．
べる．
3.
3. もし1ならGR1(1の数をカウントするレジスタ)の値
もし1ならGR1(1の数をカウントするレジスタ)の値
を1増やす．
を1増やす．
10.5
10.5 予約数の確認
予約数の確認
PRG409-A START
(1)別の解法
(1)別の解法
LAD
GR1,0
•• A←RES
A←RES
LD
GR0,RES
•• 次の３つの演算を行うと、
LAD
GR1,1,GR1 ;+1
次の３つの演算を行うと、
LOOP
LD
GR2,GR0
;GR2=A
Aの右端の1が一つ消える
Aの右端の1が一つ消える
JZE
FINISH
1.
1. B←A-1
B←A-1
LAD
GR2,-1,GR2;-1
2.
2. A←A・B
A←A・B
AND
GR0,GR2 ;GR0=A・B
•• この操作をAが０になるま
LAD
GR1,1,GR1
この操作をAが０になるま
JUMP
LOOP
で繰り返す。
で繰り返す。
FINISH
ST
GR1,COUNT
•• 繰り返しの回数が予約数
繰り返しの回数が予約数
…
例
A =0011 0100 0100 0000
B =0011 0100 0011 1111
A・B=0011 0100 0000 0000
RES
COUNT
RET
DS
DS
…
END
1
1
16
10.6
10.6 座席番号の確認
座席番号の確認
座席番号
RES
0
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15
0 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0
予約済みの座席番号の中で最大のものを出力
予約済みの座席番号の中で最大のものを出力
1.
1. そのためにはまずRESに含まれる1番右にある1を取
そのためにはまずRESに含まれる1番右にある1を取
り出す
り出す
2.
2. 次に，その1の位置(ビット位置)を計算
次に，その1の位置(ビット位置)を計算
10.6
10.6 座席番号の確認
座席番号の確認
(1)
(1) 1番右にある１の取り出し
1番右にある１の取り出し
座席番号
0
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15
RES
0 0 1 0 0 0 1 1 0 0 1 1 0 0 0
前述と同様の手法がとれる。
PRG410 START
前述と同様の手法がとれる。
…
•• A←RES
A←RES
LD
•• 次の３つの演算を行うと、
次の３つの演算を行うと、
LD
Aの右端の1が取り出せる。
Aの右端の1が取り出せる。
LAD
1.
XOR
1. B←A-1
B←A-1
AND
2.
2. B←NOT（B)
B←NOT（B)
ST
3.
3. Z←A・B
Z←A・B
…
例
A =0011
B =0011
Not(B)=1100
A・B=0000
0100
0100
1011
0000
0100
0011
1100
0100
0000
1111
0000
0000
ALLONE
RES
Z
RET
DC
DS
DS
…
END
0
GR2,RES
GR0,GR2
GR0,-1,GR0;-1
GR0,ALLONE
GR0,GR2
GR0,Z
#FFFF
1
1
17
10.6
10.6 座席番号の確認
座席番号の確認
(1)
(1) ビット位置の計算
ビット位置の計算
座席番号
0
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15
S(SINGLE) 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
L=0
S・P8
零でない
P8=0000
P8=0000 0000
0000 1111
1111 1111
1111
P4=0000
1111
0000
1111
P4=0000 1111 0000 1111
P2=0011
P2=0011 0011
0011 0011
0011 0011
0011
P1=0101
0101
0101
0101
P1=0101 0101 0101 0101
を利用する。
例:
を利用する。
例:0000
0000 0000
0000 0100
0100 0000
0000
S・P8が零でないと８加算
零でない
S・P8が零でないと８加算 零でない
S・P8が零でないと４加算
S・P8が零でないと４加算 零
零
S・P8が零でないと２加算
零
S・P8が零でないと２加算 零
S・P8が零でないと１加算
S・P8が零でないと１加算 零でない
零でない
L=L+8
零
S・P4
L=L+4
零
S・P2
L=L+2
零
S・P1
L=L+1
１１.
１１. CASLプログラミング（3つの応用）
CASLプログラミング（3つの応用）
ここまでの授業ではCASLⅡでコードを書く技術（プログラミング）を学
ここまでの授業ではCASLⅡでコードを書く技術（プログラミング）を学
んだ。
んだ。
しかし、これだけの技術ではソフトウェア製品を作ることはできない。
しかし、これだけの技術ではソフトウェア製品を作ることはできない。
ソフトウェア製品を作る場合は、次の６つの工程が必要
ソフトウェア製品を作る場合は、次の６つの工程が必要
1.1. 基本設計：
基本設計：製品構想を骨子とした基本戦略（製品の目的、対象ユーザ、使
製品構想を骨子とした基本戦略（製品の目的、対象ユーザ、使
用環境、開発言語、開発環境、開発日程など）
用環境、開発言語、開発環境、開発日程など）
2.2. 機能設計：
機能設計：外部インタフェース（入力と出力の関係、入出力の形式など）
外部インタフェース（入力と出力の関係、入出力の形式など）
3.3. 詳細設計：
詳細設計：製品の設計図にあたるものを作成（モジュール（サブリーチン構
製品の設計図にあたるものを作成（モジュール（サブリーチン構
成）、構成データの形式、データを操作するやりかた（アルゴリズム）など）
成）、構成データの形式、データを操作するやりかた（アルゴリズム）など）
4.4. プログラミング：
プログラミング：コードを記述
コードを記述
5.5. テスト仕様書：
テスト仕様書：製品が当初の目的どおり実現されたかの確認のための
製品が当初の目的どおり実現されたかの確認のための
チェック項目の作成
チェック項目の作成
6.6. テスト：
テスト：テスト仕様書に従ったテスト（机上テスト、モジュール単体テスト、モ
テスト仕様書に従ったテスト（机上テスト、モジュール単体テスト、モ
ジュール結合テスト、システムテスト）
ジュール結合テスト、システムテスト）
11.1節で、具体例をもとに詳細設計について（初歩的な）理解をする。
11.1節で、具体例をもとに詳細設計について（初歩的な）理解をする。
18
11.1
11.1 コード変換と表の検索
コード変換と表の検索
•• 機能仕様：CASLⅡの前進であるCASLのアセンブラの
機能仕様：CASLⅡの前進であるCASLのアセンブラの
命令部分を機械語に変換する。（表10.1参照）
命令部分を機械語に変換する。（表10.1参照）
LD
CASL命令
#4C44
計算機内部表現
#10
機械語命令
命令の最初の空白までの文字列（2文字～4文字）を表10.1に
従って機械語命令の最初の８ビットに変換
詳細設計の第一ステップ
詳細設計の第一ステップ
•• 概略のモジュール構成の設計と入出力の規定
概略のモジュール構成の設計と入出力の規定
スタート
LD(CASL命令)
#4C44
(計算機内部表
現）
変換
#10(機械語命令)
終了
入力：
•1語に1文字ずつ格納で、JISX201コード（8
ビット）で下位バイトに収納で、英大文字のみ
•4語の領域で、入力の文字数は２～４
•4文字に満たない場合は空白がスペース記号
のコードが挿入
•INPUT DS ４
変換：
•内部表現とコードの対応関係のテーブルを作
成し、INPUTが内部表現と一致するエントリー
のコードを出力
出力：
•1語の下位8ビット
•CODE DS １
19
詳細設計の第一ステップ
詳細設計の第一ステップ
アセンブラ全体でのモジュール構成の例
アセンブラ全体でのモジュール構成の例
スタート
入力：…….
ラベル
文字列の入力
ラベルの番地の計算とコード生成
構文解析
命令
1行の認識と1行内のラベル、命令、
パラメータ、コメントの抽出
命令コードの計算
パラメータ
パラメータコードの計算
機械語の生成
コメント
出力
終了
出力１（機械語）：…….
出力２（プログラム表）： …….
詳細設計の第二ステップ(1)
詳細設計の第二ステップ(1)
•• データの構造の設計
データの構造の設計←ある程度やり方(アルゴリズム)を考えながら設計
←ある程度やり方(アルゴリズム)を考えながら設計
問題点：テーブルを内部表現そのままとすると1命令の内部表現とす
問題点：テーブルを内部表現そのままとすると1命令の内部表現とす
るとすくなくとも8ビット×４＝32ビット（2語）必要となる
るとすくなくとも8ビット×４＝32ビット（2語）必要となる
–– CASL命令を区別するだけなら最初の３文字でよい
CASL命令を区別するだけなら最初の３文字でよい
–– 各文字は8ビットだが、その内最初の4ビットは0100(#４)か
各文字は8ビットだが、その内最初の4ビットは0100(#４)か
0101(#5)だから5ビットで表現可能(スペースは00100000だから
0101(#5)だから5ビットで表現可能(スペースは00100000だから
下位5ビットは@と同じで英大文字と重ならない）
下位5ビットは@と同じで英大文字と重ならない）
→5ビット×3文字で表現可能よりテーブルを内部表現短縮計をもち
→5ビット×3文字で表現可能よりテーブルを内部表現短縮計をもち
いて1語で表現する。
いて1語で表現する。
CASL
命令
LD
ST
……
CALL
RET
内部
表現
#4C44
#5354
……
#43414C4C
#524554
機械語
表現
10
11
……
80
81
CASL
命令
LD
ST
……
CALL
RET
内部表現
短縮形
01100 00100 00000 0
10011 10100 00000 0
……
00011 00001 01100 0
10010 00101 00100 0
機械語
表現
10
11
……
80
81
20
詳細設計の第二ステップ(2)
詳細設計の第二ステップ(2)
データの構造の設計（全ての変数は定義できない。後の工程で順次追加）
データの構造の設計（全ての変数は定義できない。後の工程で順次追加）
;入力
;入力
INPUT
INPUT DS
DS44 ;INPUT(i)[15-8]=0,
;INPUT(i)[15-8]=0,
;INPUT(i)[7-0]はJISX201コード
;INPUT(i)[7-0]はJISX201コード
;4文字に満たない場合はスペース記号のコードが挿入
;4文字に満たない場合はスペース記号のコードが挿入
;出力
;出力
CODE
CODE DS
DS11 ;CODE[15-8]=0,
;CODE[15-8]=0,CODE[7-0]=機械語表現
CODE[7-0]=機械語表現
；検索テーブル
；検索テーブル
CASL
CASL DS
DS23
23 ;内部表現短縮形を格納
;内部表現短縮形を格納
;CASL(i)[15-11]=内部表現(i,1)[4-0]
;CASL(i)[15-11]=内部表現(i,1)[4-0]
;CASL(i)[10-6]=内部表現(i,2)[4-0]
;CASL(i)[10-6]=内部表現(i,2)[4-0]
;CASL(i)[5-1]=内部表現(i,3)[4-0]
;CASL(i)[5-1]=内部表現(i,3)[4-0]
COMET
COMETDS
DS23
23 ;機械語命令コードを格納
;機械語命令コードを格納
;COMET(i)[15-8]=#00,
;COMET(i)[15-8]=#00,COMET(i)[7-0]=機械語命令コード
COMET(i)[7-0]=機械語命令コード
TSIZE
DC
23
;テーブルサイズ
TSIZE DC 23 ;テーブルサイズ
詳細設計の第三ステップ
詳細設計の第三ステップ
スタート
•• アルゴリズムの設計
アルゴリズムの設計
スタート
GR0[15-11]←INPUT(0)[5-0]
GR0[10-6]←INPUT(1)[5-0]
GR0[5-1]←INPUT(2)[5-0]
GR0[1]← ０
INPUTから
短縮形を作成
GR1←０
COMETテーブルから
コードを取出しCODEに
代入
終了
順次詳細化
CASLテーブルの
検索
GR0=CASL(GR1) YES
?
NO
GR1←GR1+1
GR1>=TSIZE
?
NO
YES
CODE←COMET(GR1)
エラー処理
終了
21
11.2
11.2 ソーティング
ソーティング
T(0)
T(1)
T(2)
T(3)
T(4)
T(5)
T(6)
T(7)
ソーティング
•• アルゴリズムの設計：アルゴリズ
アルゴリズムの設計：アルゴリズ
ム（処理手順）はプログラムの性
ム（処理手順）はプログラムの性
能を大きく左右する。処理される
能を大きく左右する。処理される
データ量や要求される速度を考
データ量や要求される速度を考
えて慎重に選択すべきである。
えて慎重に選択すべきである。
•• 本節では、ソーティング問題の３
本節では、ソーティング問題の３
つのアルゴリズムを紹介して、ア
つのアルゴリズムを紹介して、ア
ルゴリズムとは何かを理解する。
ルゴリズムとは何かを理解する。
•• ソーティングとは：与えられたデー
ソーティングとは：与えられたデー
タを小さいものから順に（昇順）あ
タを小さいものから順に（昇順）あ
るいは大きいものから順（降順）
るいは大きいものから順（降順）
に並べ替えること。
に並べ替えること。
15
10
13
40
35
39
27
45
10
13
15
27
35
39
40
45
データの検索に
O(n)
O(log n)
全て検索 二分検索法
11.2
11.2 ソーティング
ソーティング
•• 二分探索法：ソーティングされたデータ配列(T(0)～T(7))に指定
二分探索法：ソーティングされたデータ配列(T(0)～T(7))に指定
した値Nがあるかないかを検索する。存在する範囲は1/2ずつ
した値Nがあるかないかを検索する。存在する範囲は1/2ずつ
絞り込んでいく。O(log
絞り込んでいく。O(log X)の計算量（Xは配列のエントリー数）
X)の計算量（Xは配列のエントリー数）
N<T(4) ?
YES
T(0)～T(3)
NO
T(4)～T(7)
N<T(2) ?
YES
T(0)～T(1)
N=T(1) ?
N=T(0)
N=T(1)
N<T(4) ?
NO
T(2)～T(3)
N=T(3) ?
N=T(2)
N=T(3)
YES
T(4)～T(5)
N=T(5) ?
N=T(4)
N=T(5)
NO
T(6)～T(7)
N=T(7) ?
N=T(6)
N=T(7)
22
(1)
(1) 選択ソート
選択ソート
選択ソートの基本戦略
選択ソートの基本戦略
•• 配列T(0～n)の中から一番小さいものを見つけT(0)
配列T(0～n)の中から一番小さいものを見つけT(0) におき、
におき、
•• 次にT(1～n)の中で一番小さいものを見つけT(2)におく。
次にT(1～n)の中で一番小さいものを見つけT(2)におく。
•• これをｎ-1回繰り返す。
これをｎ-1回繰り返す。
15
10
13
40
35
39
27
45
1
10
15
13
40
35
39
27
45
2
10
13
15
40
35
39
27
45
3
10
13
15
40
35
39
27
45
4
10
13
15
27
35
40
39
45
5
10
13
15
27
35
40
39
45
6
10
13
15
27
35
39
40
45
7
10
13
15
27
35
39
40
45
(1)
(1) 選択ソート
選択ソート
i回目開始
選択ソートの詳細アルゴリズム
選択ソートの詳細アルゴリズム
•• n-1回の繰り返しのi回目の処理手順
n-1回の繰り返しのi回目の処理手順
の設計をして、n-1回ループを回せ
の設計をして、n-1回ループを回せ
ばよい。
ばよい。
•• i回目の処理を考える（iは1からn-1
i回目の処理を考える（iは1からn-1
まで）。
まで）。
MIN←T(i-1)
j←i
MIN>T(j)
?
i=4回目の動作例
j=4
10
13
MIN
15
=40
40
35
39
27
45
j=4
10
13
MIN
15
=35
40
40
39
27
45
NO
j=4
10
13
MIN
15
=35
40
40
39
27
j=4
10
13
MIN
15
=27
40
40
39
35
45
45
10
13
15
27
40
39
35
45
YES
MINとT(j)
を入れ替える
j←j+1
NO
j>=n
?
YES
T(i-1)←MIN
i回目終了
23
(1)
(1) 挿入ソート
挿入ソート
挿入ソートの基本戦略
挿入ソートの基本戦略
•• i回目のループの開始時にT(0～i-1)までのデータ(i個のデータ）は
i回目のループの開始時にT(0～i-1)までのデータ(i個のデータ）は
ソートされていることは同様
ソートされていることは同様
•• i回目のループでは、T(0～i-1)の適当な位置にT(i)を挿入してT(0
i回目のループでは、T(0～i-1)の適当な位置にT(i)を挿入してT(0
～i)までソートされているようにする。
～i)までソートされているようにする。
•• このループをｎ-1回繰り返す。
このループをｎ-1回繰り返す。
15
10
13
40
35
39
27
45
1
10
15
13
40
35
39
27
45
2
10
13
15
40
35
39
27
45
3
10
13
15
40
35
39
27
45
4
10
13
15
35
40
39
27
45
10
13
15
35
39
40
27
45
5
6
10
13
15
27
35
39
40
45
7
10
13
15
27
35
39
40
45
(1)
(1) 挿入ソート
挿入ソート
i回目開始
選択ソートの詳細アルゴリズム
選択ソートの詳細アルゴリズム
INS←T(i)
j←i-1
•• n-1回の繰り返しのi回目の処理手順
n-1回の繰り返しのi回目の処理手順
の設計をして、ｎ-1回ループを回せ
の設計をして、ｎ-1回ループを回せ
ばよい。
ばよい。
•• i回目の処理を考える。
i回目の処理を考える。
i=4回目の動作例
10
13
15
10
13
40
40
40 j=2
39
27 INS
45 =35
35 j=3
39
27 INS
45 =35
15
10
13
15
35
40
39
27
45
問題：比較
回数が最
大となる配
列のデータ
を作れ
（データ数
は８）
INS<T(j)
?
NO
YES
T(j+1)←T(j)
j←j-1
NO
YES
j<0
?
ループを途中で抜け出せるので選択ソートよりは高速である。
最悪の場合は、(n-1)(n-2)/2回の比較が必要である。
T(j+1)←INS
i回目終了
24
(1)
(1) バブルソート
バブルソート
バブルソートの基本戦略
バブルソートの基本戦略
•• 隣同士のデータ(T(i)とT(i+1))を比較してT(i)のほうが大きいと入れ
隣同士のデータ(T(i)とT(i+1))を比較してT(i)のほうが大きいと入れ
替える。
替える。
•• 上記操作をi=0からn-2まで順次行い最後まで行うと最初からまた
上記操作をi=0からn-2まで順次行い最後まで行うと最初からまた
比較する。
比較する。
•• 最初から最後まで入れ替えが行わないとソートが終了した。
最初から最後まで入れ替えが行わないとソートが終了した。
10
13
15
27
35
39
40
45
入替０回
10
13
15
35
27
39
40
45
入替１回
10
13
15
35
39
27
40
45
入替１回
入替５回
15
10
13
40
35
39
27
45
10
13
15
27
35
39
40
45
比較回数は
かなり減少
するような気
がする。一
番下に最少
値がある場
合は(n-1)n
回の比較が
必要である。
ソートのまとめ
ソートのまとめ
バブルソートの詳細アルゴリズムは省略する。
バブルソートの詳細アルゴリズムは省略する。
３つのアルゴリズムを紹介した。平均的な処理速
３つのアルゴリズムを紹介した。平均的な処理速
度は３つで違うが、いずれも最悪の場合、オーダ
度は３つで違うが、いずれも最悪の場合、オーダ
ｎ二乗の処理時間がかかる。
ｎ二乗の処理時間がかかる。
•• 世の中には、もっとよいアルゴリズムがある。そ
世の中には、もっとよいアルゴリズムがある。そ
のオーダはn*log
のオーダはn*log nn である。→アルゴリズム理論
である。→アルゴリズム理論
（データ量が小さい時は今回のアルゴリズムでもよ
（データ量が小さい時は今回のアルゴリズムでもよ
いが、データ量が大きくなると遅すぎて使い物に
いが、データ量が大きくなると遅すぎて使い物に
2
ならない。例えばデータの量が千とするとn
は１
ならない。例えばデータの量が千とするとn2 は１
００万で、
００万で、 n*log
n*log22nは1万であり、100倍も開く。
nは1万であり、100倍も開く。
データ量が大きくなるもっと開く。）
データ量が大きくなるもっと開く。）
••
••
25
11.3
11.3 パリティチェック
パリティチェック
•• データを通信回線で送る場合，雑音によってデータの一部の
データを通信回線で送る場合，雑音によってデータの一部の
ビット1が0になったり，ビット0が1になったりする伝送誤り
ビット1が0になったり，ビット0が1になったりする伝送誤り
が発生する．こうした伝送誤りを検出したり，(検出した誤
が発生する．こうした伝送誤りを検出したり，(検出した誤
りを)訂正したりする手法の1つにパリティチェックがある．
りを)訂正したりする手法の1つにパリティチェックがある．
•• 送りたいデータをa
…, aannのnビットとする．送り側はこ
のnビットとする．送り側はこ
送りたいデータをa11,, aa22,, …,
れにa
(パリティビットという)を余分に付加する．しかもパ
れにa00(パリティビットという)を余分に付加する．しかもパ
リティビットa
リティビットa00の値は必ずa
の値は必ずa00⊕a
⊕a11⊕a
⊕a22⊕…⊕a
⊕…⊕ann=0となるように
=0となるように
決める．一方，a
⊕a
⊕a
⊕…⊕a
=1と決める方式もある．前
決める．一方，a00⊕a11⊕a22⊕…⊕ann=1と決める方式もある．前
者を偶数パリティ，後者を奇数パリティと呼ぶ．
者を偶数パリティ，後者を奇数パリティと呼ぶ．
側
側
an
信
信
a１
a２
受
送
a0
•a1, a2, …, anを送る時その1の個数
が奇数の時a1を１、偶数の時０を
送るのが偶数パリティという。
•１ビットの誤りだけであれば、そ
の誤りを検出することができる。
（誤った場合、１の個数が奇数とな
るこにより検出）
11.3
11.3 パリティチェック
パリティチェック
•• 16ビットのデータA=
)の右側15ビットに
16ビットのデータA= (a
(a00,,aa11,,aa22,,…a
…a15
15 )の右側15ビットに
データがあるとき、16ビットの１の個数が偶数になるよう
データがあるとき、16ビットの１の個数が偶数になるよう
に最左ビットを計算するプログラムを考える。
に最左ビットを計算するプログラムを考える。
•• aa1⊕a
⊕…⊕a を計算した結果をｄ
とすればｄ が求め
1⊕a22⊕…⊕a15
15 を計算した結果をｄ00とすればｄ00が求め
る最左ビットである。
る最左ビットである。
•• aa0 =0としたデータをBとし、Aを1ビットシフトしてXORを１５
0 =0としたデータをBとし、Aを1ビットシフトしてXORを１５
回とれば答えは求まる。もっと早い方法はないか？
回とれば答えは求まる。もっと早い方法はないか？
•• XOR命令では16ビット各々で排他的論理和⊕の演算が
XOR命令では16ビット各々で排他的論理和⊕の演算が
行われている。これをうまく利用できないか？
行われている。これをうまく利用できないか？
26
11.3
11.3 パリティチェック
パリティチェック
初期化：X,Y←A
初期化：X,Y←Aand
and#8000
#8000
•• Xを8ビット左シフトし、
Xを8ビット左シフトし、 X,Y←X⊕Y
X,Y←X⊕Y
•• Bを4ビット左シフトし、
X,Y←X⊕Y
Bを4ビット左シフトし、 X,Y←X⊕Y
•• Bを2ビット左シフトし、
Bを2ビット左シフトし、 X,Y←X⊕Y
X,Y←X⊕Y
•• Bを1ビット左シフトし、
X,Y
Bを1ビット左シフトし、 X,Y ←X⊕Y
←X⊕Y
Xの最左ビットが求める解ｄ
となる
Xの最左ビットが求める解ｄ0 となる
0
x
x0
x1
x2
x3
x4
x5
x6
x7
計算1
計算2
a8
a8⊕a4⊕a12
a1⊕a9 a1⊕a9⊕a5⊕a13
a2⊕a10 a2⊕a10⊕a6⊕a14
a3⊕a11 a3⊕a11⊕a7⊕a15
a4⊕a12
a5⊕a13
a6⊕a14
a7⊕a15
計算3
a8⊕a4⊕a12⊕a2⊕a10⊕a6⊕a14
a1⊕a9⊕a5⊕a13⊕a3⊕a11⊕a7⊕a15
計算4
a1⊕a2⊕…⊕a15
11.3
11.3 パリティチェック
パリティチェック
•• ここでは、パリティは1ビット誤りのみしか検出で
ここでは、パリティは1ビット誤りのみしか検出で
きない。ビット数が少ないデータには用いられるが、
きない。ビット数が少ないデータには用いられるが、
通信などビット数のかたまりが大きい場合には、ｍ
通信などビット数のかたまりが大きい場合には、ｍ
ビットの付加でｍビット誤りを検出できる手法が用
ビットの付加でｍビット誤りを検出できる手法が用
いられる。
いられる。 →符号理論
→符号理論
27