お茶の水女子大学 人間文化創成科学研究科 理学専攻 情報科学コース 2017年2月実施 情報基礎 問題1

标签：

• Ochanomizu-University
• Computer-Architecture
• Networks
• Channel-Coding

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

$2$ 進数 $N$ の桁数を $n$ としたとき、$N$ についての $1$ の補数 $C$ の定義は以下の通りである。

$$C=2^n-N-1.$$

1. $N=\mathtt{0x0001}$ の時、$N$ の $1$ の補数 $C$ を求めよ。またこの時の $N$ と $C$ の和を求めよ。ただし $\mathtt{0x0001}$ は $16$ 進数で $0001$ であることを表し、$2$ 進数では $0000000000000001$ となる。
2. $N=\mathtt{0x0000}$ の時、$N$ の $1$ の補数 $C$ を求めよ。
3. $1$ の補数においては、前問の $N$ と $C$ は同値であるとみなされる。この事を元に、$1$ の補数同士の和（$1$ の補数和）の計算は、桁上がりを一番右の位に足しこめば良いという事を、例を $1$ つ示して説明せよ。
4. パケット通信で使われるビットエラー検出のチェックサムの計算は、まず送信側でチェックサムフィールドに $0$ を入れて $16$ ビット単位で区切り、それぞれの $1$ の補数和を求め、その値の $1$ の補数をチェックサムフィールドに入れてパケットを送るというものである。このパケットを受け取った受信側は、どのような計算をしてビットエラーを検出するか、検出できる理由と共に説明せよ。

题目描述

对 $n$ 位二进制数 $N$，其一补数定义为 $C=2^n-N-1$。

1. 对 16 位数 $N=\mathtt{0x0001}$，求 $C$ 及 $N+C$。
2. 对 $N=\mathtt{0x0000}$，求 $C$。
3. 在一补数表示中，第 2 问的 $N$ 与 $C$ 被视为等值；基于这一事实，用一个例子说明一补数加法为何要把最高位的进位回加到最低位。
4. 说明接收方如何验证 16 位一补数校验和，并解释其检测错误的理由。

Kai

(1)

$n=16$ だから

$$C=2^{16}-1-\mathtt{0x0001} =\boxed{\mathtt{0xFFFE}}.$$

したがって

$$N+C=\mathtt{0x0001}+\mathtt{0xFFFE} =\boxed{\mathtt{0xFFFF}}.$$

これは $1$ の補数表現における負の零である。

(2)

$$C=2^{16}-1-\mathtt{0x0000} =\boxed{\mathtt{0xFFFF}}.$$

$\mathtt{0x0000}$ と $\mathtt{0xFFFF}$ は、それぞれ正の零と負の零を表す。

(3)

$4$ ビットの例として $5+(-3)$ を計算する。$3=\mathtt{0011}$ なので、その $1$ の補数は $\mathtt{1100}$ である。通常の加算を行うと

  0101   (+5)
+ 1100   (-3)
------
1 0001

となる。最上位からの桁上がり $1$ を最下位に足すと

0001 + 0001 = 0010

となり、正しく $2$ を得る。$1$ の補数では $2^n-1$ を零と同値とみなすので、$2^n$ の桁上がりは

$$2^n\equiv1\pmod{2^n-1}$$

として最下位へ戻す。これをエンドアラウンドキャリーという。

(4)

受信側も、受信したチェックサムを含むパケット全体を $16$ ビット語に分け、桁上がりを最下位へ戻しながら $1$ の補数和を計算する。

送信時、チェックサムを除く語の和を $S$ とすると、チェックサムは $\overline{S}$ である。したがって誤りがなければ

$$S+\overline{S}=\mathtt{0xFFFF}$$

となる。よって受信側の和が $\mathtt{0xFFFF}$ なら検査を通過し、それ以外ならビットエラーを検出する。特に $1$ ビットだけの誤りは必ず和を変えるので検出できる。ただし、変化が相殺される一部の複数ビット誤りは検出できない。