Java教程

计组 |二、数据的表示和运算

本文主要是介绍计组 |二、数据的表示和运算,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

[一 数制和编码](#一 数制和编码)

[二 定点数](#二 定点数)


一 数制和编码

1.数制相互转换

2.BCD码

3.字符与字符串

4.校验码

  • 奇偶校验
  • 海明码
  • 循环冗余校验码

1.数制相互转换

image-20210927232208387


1.1 r进制到十进制

image-20210927232246629

1.2 二进制到八进制、十六进制

image-20210927232316649

1.3 十进制到r进制

image-20210927232401029

2.BCD码

image-20210927232423771

3.字符与字符串

image-20210927232449905

3.1 字母存储

image-20210927232516763

3.2 汉字存储

image-20210927232520468

4.校验码

image-20210926212953782

4.1 奇偶校验

image-20210926202003212

4.2 海明码

4.2.1 求解步骤

(1)确定校验码位数

  • \(2^k\ge n+k+1(n+k为任何一位都可能出错,还有1种正确状态)\)
  • n个信息位;k个校验位,校验码有\(2^k\)种状态;

(2)确定校验码位置

  • \(P_i\)放在\(2^{i-1}\)的位置上,其余按顺序

  • 信息位\(D_4D_3D_2D_1(1010)\),校验位\(P_3P_2P_1\),海明码为\(H_7H_6H_5H_4H_3H_2H_1\)

    image-20210926194702444

(3)求校验位的值

  • 由\(H_i\)位置\(i\)算出对应的二进制码

  • 从右到左按列\(h\)观察,选出所有为1的\(H_i\)。找出\(H_i\)对应的信息位\(D_j\),对所有\(D_j\)进行异或运算,则可得出对应的\(P_h\)

    image-20210926195352566

(4)纠错

  • 对校验方程进行计算

  • 若出现偶校验错误,将结果\(S_3S_2S_1\)转为十进制,对应位置即为错误位置

    image-20210926201504716

4.2.2 检错与纠错

  • 检错能力:2;纠错能力:1

  • 全体校验

    当两个跳变时,无法根据对应的位置确定它就是出错位。即上面无法区别是1位错还是2位错。所以引入全校验位,在最后面加上\(P_全\),该值是由原始数据得出偶校验码。

    现在对传输的数据进行一次全体偶校验进行分析

    image-20210926203551403

4.3 循环冗余校验码

CRC。数据发送、接受方约定一个“除数”,保证余数为0


4.3.1 求CRC码

(1)确定长度与二进制码

  • 信息码长度K;
  • 校验码R=生成多项式最高次幂;
  • 校验码位数N=K+R
  • 二进制码:生成多项式的系数

(2)由模2除法求CRC码

  • 信息码低位补R个0(右侧)
  • 模2除法
    • 被除数:信息位+R个0
    • 除数:二进制码
    • 除的时候看最高位作为商,减的时候用异或运算。
    • 余数比被除数少一位,余数结果为校验位
  • CRC码:信息位+校验位

4.3.2 检错与纠错

  • 示例

    image-20210926211814247

  • 检错:

    可检测出所有奇数个错误;

    可检测出所有双比特的错误;

    可检测出所有小于等于校验位长度的连续错误;

  • 纠错:

    K个信息位,R个校验位,若生成多项式选择得当,且 \(2^R\ge K+R+1\),CRC码可纠正1位错。

二 定点数

1.定点数的表示

2.定点数运算

  • 补码作用
  • [移位运算](#2.2 移位运算)
  • [加法运算](#2.3 加减运算)

1.定点数的表示

image-20210927215422366

表示范围

类型 范围
无符号数(n) \(0\sim2^n-1\)
原码/反码整数(n+1) \(-(2^n-1)\le x\le 2^n-1\)
原码/反码小数(n+1) \(-(1-2^{-n})\le x\le 1-2^{-n}\)
补码/移码整数(n+1) \(-2^n\le x\le2^n-1\\比原码多表示一个-2^n\)
补码小数(n+1) \(-1\le x\le1-2^-n\\比原码多一个-1\)

2.定点数运算

2.1 补码作用

减法换加法,减少硬件成本(ALU无需集成减法器)


\(带余除法:\\x=qm+r\\x~mod~12=r\\(q为整数,r为余数,m为模。类似周期,即要在r相等的情况下找到x)\)

  • 模余数相同的数是同一类,等价。即可知-3和9在模12的条件下是等价的。
  • 互为补数:两个数的绝对值=模。减去一个数即加上这个数的补数。也就是\(10+(-3)\)可转换成\(10+9\)再取模。
  • 而计算机是以\(2^8(1,00000000)\)为模的,[a]补=模-|a|=全部取反再+1

image-20210927150727185

2.2 移位运算

image-20210927215546058

2.2.1 算数移位

image-20210927153015895


补码的算数移位

  • 正数和原码一致

  • 由于负数补码=反码末位+1。所以反码最右边连续的1会因进位变成0,直到第一个0。故负数补码最右边的1及其右边与原码一致。而其左边与反码一致。所以造成了:

    • 右移(同反码):高位补1,低位舍弃。
    • 左移(同原码):低位补0,高位舍弃。

image-20210927152929678


加法举例

image-20210927153138008

2.2.2 逻辑移位

RGB值例子:例如用3B储存102、139、133

102的二进制数储存进去并向左移动16位

139的二进制数储存进去并向左移动8位

133的二进制数储存进去

相加得3B的RGB值

2.2.3 循环移位

image-20210927153644315

2.3 加减运算

加减运算

2.3.1 溢出判断

image-20210927221346287


  • 方法一:一位符号位

    \[V=AB\overline{S}+\overline{AB}S\\加数的符号位为:A、B;结果的符号位S:(乘法表示与,加法表示或) \]

  • 方法二:一位符号位,根据进位情况判断

    \[V=C_1\oplus C_s\\ 结果的最高数值位的进位:C_1;符号位的进位:C_s; \]

  • 方法三:双符号位

    \[V=S_{s1}\oplus S_{s2}\\正数符号位:00;负数符号位11;\\结果的两个符号位分别是S_{s1}S_{s2} \]

    ==>V=0无溢出;V=1溢出

2.3 乘法运算

乘数从左到右依次乘以被乘数,每次都要错位

  • 原码一位乘法

    符号位进行异或运算

    数值位取绝对值进行乘法运算

    ACC乘积高位

    MQ乘数、乘积低位

    X被乘数

    ACC置0

    MQ最右一位开始:1-》ACC+被乘数;0-》ACC加上0

    通过ALU,结果放在ACC寄存器

    ACC MQ逻辑右移。之后运算过程像上面一样

    部分积:逻辑右移后放在MQ的位

    重复数值位n次

    结果:ACC与MQ组合,第一位为符号位,后面为小数部分

    处理符号位

    对于整数的,符号位是最右边的一位

    ---n论加法,移位

    --根据MQ最低位确定加什么。加法可能是+0、+[x]原码

  • 补码一位乘法

    n轮加法,移位,再一次加法

    --根据MQ最低位和辅助位确定加什么。

    ​ 辅助位-最低位=1----+0

    ​ 辅助位-最低位=0----+[x]补

    ​ 辅助位-最低位=-1----+[-x]补

    --算数右移

    --正负不用异或约定

这篇关于计组 |二、数据的表示和运算的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!