Table of Contents

  1. Algorithm
  2. Review
    1. 模块、源文件和包
    2. 访问层级
    3. 访问层级的指导原则
    4. 缺省访问层级
      1. 单目标 app 的访问层级
      2. 库的访问层级
      3. 目标单元测试的访问层级
    5. 访问控制语法
    6. 自定义类型
      1. 元组类型
      2. 函数类型
      3. 枚举类型
      4. 裸值和关联值
      5. 嵌套类型
      6. 子类化
      7. 常量、变量、属性和下标
      8. Getter 和 Setter
      9. 初始化函数
      10. 缺省初始化函数
      11. 对结构类型的缺省成员初始化函数
      12. 协议
      13. 协议继承
      14. 协议遵从
      15. 扩展
      16. 扩展中的 private 成员
      17. 范型
      18. 类型别名
  3. Tips
    1. 位操作
      1. NOT 操作
      2. AND 操作
      3. OR 操作
      4. XOR 操作
      5. 位左移和右移操作
      6. 溢出操作
      7. 操作符方法
      8. 前置和后置操作
      9. 复合赋值操作
      10. 相等操作
      11. 自定义操作符
      12. 自定义 Infix 操作符的优先级
    2. 结果构建器
  4. Share
    1. 功能
    2. 发明
    3. 历史和实际的应用程序
      1. 数学谜
      2. 电报代码
      3. 模拟到数字信号转换
      4. 位置编码器
      5. 基因算法
      6. 布尔电路最小化
      7. 错误矫正
      8. 时钟域间的通信
      9. 最小影响的通过状态循环
    4. 构建一个 n 位 Gray code
    5. 转换成 Gray code 和从 Gray code 转换
    6. Gray code 的特殊类型
      1. n 位 Gray code 且长度小于 $ 2n $
      2. n 进制 Gray code
      3. 平衡 Gray code
      4. 长运行 Gray code
      5. 单调 Gray code
      6. Beckett-Gray code
      7. 箱中蛇代码
      8. 单轨 Gray code
      9. 两维 Gray code
      10. 过量 Gray code
    7. Gray 等距映射

Algorithm

Leetcode 1234: Replace the Substring for Balanced String

https://dreamume.medium.com/leetcode-1234-replace-the-substring-for-balanced-string-9885b4a64adf

Review

Access Control

访问控制从代码中在其他源文件和模块中限制访问你的代码部分。这个特性使得你隐藏你代码的实现细节,且指定一个更好的接口让代码访问和使用

你可赋值特别的访问层级到私有类型(类、结构和枚举),和属于这些类型的属性、方法、初始化函数和下标。协议可限制到某个上下文,可为全局常量、变量和函数

另外提供各种访问控制层级,Swift 通过提供类型场景的默认访问层级来缩减直接指明访问控制层级的需要。事实上,如果你写单个 app,你可完全不需要指明访问控制层级

模块、源文件和包

Swift 的访问控制模型基于模块、源代码和包的概念

一个模块是代码分发的一个单元 - 一个 framework 或应用程序且可用 Swift 的 import 关键字在其他模块导入

在 Xcode 中每个构建目标在 Swift 被作为一个独立模块处理。如果你收集你的应用程序代码作为一个独立 framework - 也许跨多个应用程序封装和重用代码 - 则 framework 里你定义的所有将为一个独立模块的一部分当它导入并使用在一个 app 中时,或被另一个 framework 使用

一个源文件是一个模块里的一个 Swift 源代码文件。虽然通常在独自的源文件中定义独立的类型,一个源文件可包含多个类型、函数等的定义

一个包是你开发的一组模块作为一个单元。你定义模块作为你使用的配置构建系统的一部分,而不是你 Swift 源代码的一部分。例如,如果你使用 Swift 包管理器构建你的代码,你在你的 Package.swift 文件里定义一个包使用 PackageDescription 模块里的 API,且如果你使用 Xcode,你在包访问唯一标识符构建设置里指明包名称

访问层级

Swift 对你的代码提供六种不同的访问层级。这些访问层级对条目定义的源文件,源文件所属的模块和模块所属的包相关

  • open 访问和 public 访问使在条目定义的模块中的任意源文件和导入该定义模块其他模块源文件可以使用该条目。典型地你在指明一个公共接口到库时使用 open 或 public 访问
  • 包访问使得条目用于定义它们的包里的任意源文件,其他包源文件则不允许。你典型地在 app 或结构化为多个模块的库中使用包访问
  • 内部访问使条目用于定义它们的模块的任意源文件中,其他源文件则不允许。你典型地当定义一个 app 的或库的内部结构时使用内部访问
  • 文件私有访问限制条目用于定义它的源文件里。使用文件私有访问隐藏一个特殊功能的细节实现,其细节用于整个文件
  • 私有访问限制条目的使用在相同文件中相关定义域和定义扩展中。使用私有访问隐藏一个特殊功能的实现细节,其细节只用于单个定义中

open 访问是最高访问层级且私有访问是最低访问层级

open 访问只应用于类和类成员,且它跟公开访问不同,允许模块外的代码对其子类化和覆盖。标记一个类为 open 直接表示你考虑这个类作为父类在其他模块中的影响,且合理地设计你的类代码

访问层级的指导原则

在 Swift 中的访问层级遵循一个总的指导原则:没有条目可用另一个更低访问层级的条目定义

例如:

  • 一个 public 变量不能有一个内部、文件私有或私有类型,因为类型可能不会在公开变量的任意位置有效
  • 一个函数不能有比它的参数类型和返回类型更高的访问层级,因为函数可能用于当它的组成类型对周围代码无效的情况

这个指导原则的特别间接说明对语言的其他方面的具体细节在后续章节描述

缺省访问层级

你代码的所有条目当你不直接指定访问层级时有一个内部的缺省访问层级

单目标 app 的访问层级

当你写一个简单的单目标 app,你的程序代码典型地被 app 自包含且不需要在 app 模块外部有效。内部的缺省访问层级已经匹配这个需求。因此,你不需要指明一个自定义的访问层级。你可,想要标记你的代码的一些部分作为文件私有或私有来对 app 模块的其他代码隐藏它们的实现细节

库的访问层级

当你开发一个库,标记一个开放接口作为 open 或 public 这样它可被其他模块看到和访问,这样一个 app 可导入这个库。这样这个开放接口是库的应用程序编程接口

目标单元测试的访问层级

当你用一个单元测试目标写一个 app,你的 app 代码需要对该模块有效来测试。缺省,只有标记为 open 或 public 的条目可被其他模块访问。然而,一个单元测试目标可访问任意内部条目,如果你对一个产品模块用 @testable 属性标记导入定义并用测试启动属性来编译该产品模块

访问控制语法

通过在条目定义的开头摆放 open、public、internal、fileprivate 或 private 修饰符来定义一个条目的访问层级

open class SomeOpenClass {}
public class SomePublicClass {}
internal class SomeInternalClass {}
fileprivate class SomeFilePrivateClass {}
private class SomePrivateClass {}

open var someOpenVariable = 0
public var somePublicVariable = 0
internal let someInternalConstant = 0
fileprivate func someFilePrivateFunction() {}
private func somePrivateFunction() {}

除非已指定,缺省的访问层级是 internal。这意味着 SomeInternalClass 和 someInternalConstant 可不用直接指定访问层级修饰符,将会有 internal 的访问层级

class SomeInternalClass {}              // implicitly internal
let someInternalConstant = 0            // implicitly internal

自定义类型

如果你想要对一个自定义类型指定一个访问层级,在定义它的时候指定。当新类型的访问层级允许时它就可用。例如,如果你定义一个 file-private 类,该类只能用于属性类型或函数参数或返回类型,在 file-private 类定义的文件中

一个类型的访问控制层级也影响该类成员(它的属性、方法、初始化函数和下标)的缺省访问层级。如果你定义一个类型的访问层级为 private 或 file private,它的成员的缺省访问层级将也为 private 或 file private。如果你定义一个类型的访问层级为 internal 或 public(或不直接指定一个访问层级使用 internal 的缺省访问层级),类型成员的缺省访问层级为 internal

重要:一个公开类型缺省有 internal 的成员,而不是 public 的成员。如果你想要一个类型成员为 public,你必须直接标记它为 public。这个需求确保一个类型的公开 API 是你选择发布的,且避免错误地呈现一个类型的内部工作作为公开接口

public class SomePublicClass {                   // explicitly public class
    public var somePublicProperty = 0            // explicitly public class member
    var someInternalProperty = 0                 // implicitly internal class member
    fileprivate func someFilePrivateMethod() {}  // explicitly file-private class member
    private func somePrivateMethod() {}          // explicitly private class member
}

class SomeInternalClass {                        // implicitly internal class
    var someInternalProperty = 0                 // implicitly internal class member
    fileprivate func someFilePrivateMethod() {}  // explicitly file-private class member
    private func somePrivateMethod() {}          // explicitly private class member
}

fileprivate class SomeFilePrivateClass {         // explicitly file-private class
    func someFilePrivateMethod() {}              // implicitly file-private class member
    private func somePrivateMethod() {}          // explicitly private class member
}

private class SomePrivateClass {                 // explicitly private class
    func somePrivateMethod() {}                  // implicitly private class member
}

元组类型

对一个元组类型的访问层级是使用在该元组中所有类型里最受限的访问层级。例如,如果你从两个不同类型拼装一个元组,一个为 internal 访问层级另一个为 private 访问层级,则组合的元组类型访问层级将为 private

注意 元组类型没有像类、结构、枚举和函数那样独立的定义。一个元组类型的访问层级自动从构成元组类型的类型中确定,且不能直接指定

函数类型

一个函数类型的访问层级是函数参数和返回类型中最受限的访问层级。你必须直接指定访问层级作为函数的定义如果函数的计算访问层级不匹配缺省的上下文时

下面例子定义一个全局函数称为 someFunction(),没有对函数本身提供一个指定的访问层级修饰符。你可期望这个函数有 internal 的缺省访问层级,但并不是。事实上,someFunction() 不会通过编译

func somefunction() -> (SomeInternalClass, SomePrivateClass) {
    // function implementation goes here
}

函数的返回值是一个元组类型由两个自定义类组成。一个类定义为 internal,另一个定义为 private。因此,复合元组类型总的访问层级是 private

因为函数的返回类型是 private,你必须标注函数的总访问层级为 private 到函数定义才有效

private func someFunction() -> (SomeInternalClass, SomePrivateClass) {
    // function implementation goes here
}

用 public 或 internal 修饰符标注 someFunction() 的定义是无效的,因为 函数的 public 或 internal 用户不能合适地访问函数返回类型中的 private 类

枚举类型

一个枚举的独立值自动接受它们所属的枚举的相同的访问层级。你不能对一个独立枚举值指定一个不同的访问层级

在下面例子中,CompassPoint 枚举有一个直接的访问层级 public。枚举值 north、south、east 和 west 因此也有访问层级 public

public enum CompassPoint {
    case north
    case south
    case east
    case west
}

裸值和关联值

在枚举中定义的用于任意裸值或关联值的类型必须有一个访问层级至少跟枚举的访问层级一样高。例如,你不能使用一个 private 类型作为一个 internal 类型枚举的裸值类型

嵌套类型

一个嵌套类型的访问层级跟它包含的类型一样,除非包含类型是 public。嵌套类型在一个 public 类型中定义有一个 internal 的自动访问层级。如果你想要一个 public 的嵌套类型为公开有效,你必须直接声明嵌套类型为 public

子类化

你可子类化在当前访问上下文和定义在相同模块中的任意类作为子类。你可子类不同模块下任意 open 类。一个子类不能有比它的父类更高的访问层级 - 例如,你不能写一个 internal 父类的一个 public 子类

另外,对定义在相同模块的类,你可覆盖在某个访问上下文中可见的任意类成员(方法、属性、初始化函数或下标)。对定义在另一个模块中的类,你可覆盖任意 open 类成员

一个覆盖可使得一个继承类成员比它的父类版本更可访问。在下面例子中,类 A 是一个 public 类带一个 file-private 的方法称为 someMethod()。类 B 是类 A 的子类,带一个 internal 的访问层级。尽管,类 B 提供一个带 internal 访问层级的覆盖的 someMethod() 方法,其访问层级高于原始实现的 someMethod() 访问层级

public class A {
    fileprivate func someMethod() {}
}

internal class B: A {
    override internal func someMethod() {}
}

一个子类成员调用一个比子类成员访问层级小的父类成员也是有效的,调用父类成员发生在一个允许的访问层级上下文(在相同源代码下父类一个 file-private 成员调用,或在相同模块下父类一个 internal 成员调用):

public class A {
    fileprivate func someMethod() {}
}

internal class B: A {
    override internal func someMethod() {
        super.someMethod()
    }
}

因为父类 A 和子类 B 定义在相同的源代码文件中,对 B 的 someMethod() 实现调用父类的 super.someMethod() 方法是有效的

常量、变量、属性和下标

一个常量、变量或属性不能比它的类型更公开。写一个私有类型的 public 属性是无效的。相似的,一个下标不能比它的索引类型或返回类型更公开

如果一个常量、变量、属性或下标用一个私有类型,常量、变量、属性或下标必须也标注为私有

private var privateInstance = SomePrivateClass()

Getter 和 Setter

常量、变量、属性和下标的 Getter 和 Setter 自动收到属于它们的常量、变量、属性或下标的访问层级

你可给出一个 setter 比它对应的 getter 更低的访问层级,来限制变量、属性或下标的读写范围。你给定一个更低的访问层级通过写 fileprivate(set)、private(set)、internal(set) 或 package(set) 在 var 或 subscript 之前

注意 这个规则应用到存储属性也用于计算属性。甚至你不对一个存储属性直接写 getter 和 setter,Swift 仍会同步一个间接的 getter 和 setter 来提供访问存储属性背后的存储。使用 fileprivate(set)、private(set)、internal(set) 和 package(set) 来改变这个同步 setter 的访问层级,这在计算属性上也一样

下面例子定义一个结构称为 TrackedString,其保存 string 属性修改的次数:

struct TrackedString {
    private(set) var numberOfEdits = 0
    var value: String = "" {
        didSet {
            numberOfEdits += 1
        }
    }
}

TrackedString 结构定义一个存储字符串属性称为 value,初始值为 ““。结构也定义一个存储整型属性称为 numberOfEdits,用来跟踪 value 修改的次数。这个修改用 value 上的 didSet 属性观察者实现,在 value 属性设置一个新值时增一

TrackedString 结构和 value 属性不提供一个直接的访问层级修饰符,且这样它们都接收 internal 的缺省访问层级。然而,numberOfEdits 属性的访问层级用一个 private(set) 标注来表明属性的 getter 还是缺省的访问层级,但属性只在 TrackedString 结构代码里可修改。这使得 TrackedString 在内部修改 numberOfEdits 属性,但在结构定义之外呈现为只读属性

如果你创建一个 TrackedString 实例并修改它的 value 值几次,你可看到 numberOfEdits 属性值跟修改次数一样

var stringToEdit = TrackedString()
stringToEdit.value = "This string will be tracked."
stringToEdit.value += " This edit will increment numberOfEdits."
stringToEdit.value += " So will this one."
print("The number of edits is \(stringToEdit.numberOfEdits)")
// Prints "The number of edits is 3"

注意你可按需要对 getter 和 setter 设置一个直接的访问层级。下面例子显示一个 TrackedString 结构版本,该结构定义为指定的 public 访问层级。结构的成员因此有 internal 的默认访问层级。你可使结构的 numberOfEdits 属性 getter 为 public,且 setter 为 private,组合 public 和 private(set) 访问层级修饰符

public struct TrackedString {
    public private(set) var numberOfEdits = 0
    public var value: String = "" {
        didSet {
            numberOfEdits += 1
        }
    }
    public init() {}
}

初始化函数

自定义初始化函数可被赋予一个访问层级小于或等于它们初始化的类型。唯一的例外是需求初始化函数。一个需求初始化函数必须有属于它的类的一样的访问层级

对于函数和方法参数,一个初始化函数的参数类型不能比初始化函数本身的访问层级更小

缺省初始化函数

Swift 对任意结构或基类自动提供一个没有任何参数的缺省初始化函数,其设置所有它的属性的初始值且不提供至少一个初始化函数

一个缺省初始化函数有它初始化类型相同的访问层级,除非类型定义为 public。对定义为 public 的类型,缺省初始化函数为 internal。如果你想要一个 public 类型

对结构类型的缺省成员初始化函数

结构类型的缺省成员初始化函数在任意结构的存储属性为 private 时其也为 private。同样的,如果任意结构的存储属性为 file private,则该初始化函数也为 file private。否则,该初始化函数为 internal

如果你想要在另一个模块里使用一个 public 的结构类型用成员初始化函数来初始化,你必须在类型的定义中提供一个 public 的成员初始化函数

协议

如果你想要给一个协议类型直接赋值一个访问层级,你要在协议定义的时候做。这使得你创建的协议只适配某种访问上下文

在一个协议里定义的每一个需求的访问层级自动设置为该协议相同的访问层级。你不能设置一个协议需求为不同于协议支持的其他访问层级。这确保所有协议的需求在任意适配协议的类型上都可见

注意 如果你定义一个 public 的协议,协议的需求当实现时需要一个 public 的访问层级。这个行为跟其他类型不同,其他类型的定义意味着对类型成员的间接的 internal 的访问层级

协议继承

如果你定义一个新协议继承自一个现存的协议,新协议最多有跟它继承的协议有相同的访问层级。例如,你不能写一个 public 的协议是从一个 internal 的协议继承的

协议遵从

一个类型可用比本身更低的访问层级遵从一个协议。例如,你可定义一个 public 的类型用于其他模块,其遵从一个 internal 的协议只能用在该协议定义的模块中

一个类型遵从一个特殊协议的上下文的访问层级是类型的访问层级和协议的访问层级的最小者。例如,如果一个类型是 public,但它遵从的一个协议是 internal,类型对该协议的遵从也是 internal

当你写或扩展一个类型遵从一个协议,你必须确保每个协议需求的类型的实现有至少跟类型遵从该协议相同的访问层级。例如,如果一个 public 的类型遵从一个 internal 协议,每个协议需求的类型的实现必须至少是 internal

注意 在 Swift 中,和 Objective-C 一样,协议遵从是全局的 - 它不能说一个类型在相同的程序中以两种不同的方式遵从一个协议

扩展

你可扩展一个类、结构或枚举在该类、结构或枚举有效的任意访问上下文中。添加到扩展中的任何类型成员有跟原始被扩展类型的类型成员有相同的缺省访问层级。如果你扩展一个 public 或 internal 类型,任何你添加的新的类型成员有一个缺省的 internal 的访问层级。如果你扩展一个 file-private 类型,你添加的任何新类型成员有一个 file-private 的缺省访问层级。如果你扩展一个 private 类型,你添加的任何新的类型成员将有一个 private 的默认访问层级

另外,你可用一个直接的访问层级修饰符标注一个扩展(例如,private)来设置定义在扩展中所有成员的一个新的默认访问层级。这个新的缺省可覆盖扩展的独立类型成员

如果你使用扩展来添加协议遵从,你不能给扩展提供一个直接的访问层级修饰符。而是,协议的自己的访问层级用来提供扩展中对每个协议需求实现的缺省访问层级

扩展中的 private 成员

扩展跟被扩展的类、结构或枚举在相同的文件中,就像扩展中的代码作为原始类型定义的一部分。结果,你可:

  • 在原始声明中定义一个 private 成员,且在相同文件中扩展可访问该成员
  • 在一个扩展中声明一个 private 成员,在相同文件中其他扩展可访问该成员
  • 在一个扩展中声明一个 private 成员,在相同文件中从原始声明中访问该成员

这个行为意味着你可使用扩展组织你的代码,不管你的类型有 private 的条目。例如,给出下面的简单协议:

protocol SomeProtocol {
    func doSomething()
}

你可使用扩展来添加协议遵从,如下:

struct SomeStruct {
    private var privateVariable = 12
}

extension SomeStruct: SomeProtocol {
    func doSomething() {
        print(privateVariable)
    }
}

范型

一个范型类型或范型函数的访问层级是范型类型或函数本身的访问层级和在它的类型参数上任意类型限制的访问层级的最小值

类型别名

任意你定义的类型别名因访问控制的原因作为一个不同的类型对待。一个类型别名可有其被别名的类型的相同或低于其的访问层级。例如,一个 private 类型别名可设置为 private、file-private、internal、public 或 open 类型,但一个 public 类型别名不能被 internal、file-private 或 private 类型的来别名

注意 这个规则也应用于用来满足协议遵从的关联类型的类型别名

Tips

Advanced Operators

Swift 提供了一些高级操作执行更加复杂的值操作。这些包括你在 C 或 Objective-C 中熟悉的位和位移操作

跟 C 的算数操作不同,Swift 中的算术操作缺省不溢出。溢出行为被设陷并报道为一个错误。要选择溢出行为,使用 Swift 的第二个集合的缺省算术操作,比如溢出加法操作(&+)。所有这些溢出操作以 & 符号开头

当你定义你自己的结构、类和枚举,对这些自定义类型提供你自己的标准 Swift 操作实现是很有用的。Swift 很容易提供这些操作的尾实现并精确决定对每个你创造的类型应该用什么行为

你不限制预定义操作,Swift 给你自由来定义你自己的自定义 infix、prefix、postfix 和赋值操作,用自定义的优先级和相关值。这些操作可用于适配在你的代码里跟任意预定义操作一样,且你可甚至扩展现存的类型来支持你定义的自定义操作

位操作

位操作使你在一个数据结构中操作独立的裸数据位。通常使用在底层编程中,比如图形编程和创建设备驱动。位操作在你从外部源中操作裸数据时也很有用,比如从一个自定义协议中编码和解码通信数据

Swift 支持所有 C 语言中的位操作

NOT 操作

NOT 操作是一个前置操作符,反转所有数字中的位

let initialBits: UInt8 = 0b00001111
let invertedBits = ~initialBits  // equals 11110000

AND 操作

AND 操作组合两个数字的位

let firstSixBits: UInt8 = 0b11111100
let lastSixBits: UInt8  = 0b00111111
let middleFourBits = firstSixBits & lastSixBits  // equals 00111100

OR 操作

OR 操作比较两个数字的位

let someBits: UInt8 = 0b10110010
let moreBits: UInt8 = 0b01011110
let combinedbits = someBits | moreBits  // equals 11111110

XOR 操作

XOR 操作异或两个数字的位

let firstBits: UInt8 = 0b00010100
let otherBits: UInt8 = 0b00000101
let outputBits = firstBits ^ otherBits  // equals 00010001

位左移和右移操作

  1. 无符号整数的移动操作

    无符号整数的位移行为如下:

    1. 根据需求将现存的位左移或右移
    2. 移出超过整数存储边界的任意位被丢弃
    3. 左移或右移后空出来的位插入 0

      let shiftBits: UInt8 = 4 // 00000100 in binary shiftBits « 1 // 00001000 shiftBits « 2 // 00010000 shiftBits « 5 // 10000000 shiftBits « 6 // 00000000 shiftBits » 2 // 00000001

  2. 有符号整数的移动行为

    有符号整数使用第一个位(称为符号位)来表示整数为正还是负。一个符号位为 0 表示正,否则表示负

    剩下的位(称为值位)存储实际的值。正数存储跟无符号一致

    负数则不同,它们存储为用 2 的 n 次方减去它们的绝对值,n 是值位的个数

    这种负数的编码被称为 2 的补码表示,它有几个优点

    首先,两个负数相加可操作为所有位的标准二进制加法,并丢弃溢出位

    其次,2 的补码表示法让你左移或右移操作时跟正数相同,而对于左移,有一个额外的规则,左移后空出来的位需要填 1

溢出操作

如果你尝试插入一个数到一个整型常量或变量而导致不能持有该值,Swift 默认会报道一个错误而不是允许一个非法的值创建。当你操作过大或过小的数时这个行为给了你额外的安全性

例如,Int16 整数类型持有的值范围为 -32768 到 32767。尝试设置超过这个范围将导致一个错误

var potentialOverflow = Int16.max
// potentialOverflow equals 32767, which is the maximum value an Int16 can hold
potentialOverflow += 1
// this causes an error

当编程边界值条件时提供错误处理使得你有更多的灵活性

然而,当你指明想要一个溢出条件来截断数的有效位时,你可选择这个行为而不是触发一个错误。Swift 提供三个算术溢出操作来在整数计算中选择溢出行为:

  • 溢出加法(&+)
  • 溢出减法(&-)
  • 溢出乘法(&*)

操作符方法

类和结构可提供它们自己的现存操作符的实现

下面例子显示对一个自定义类型如何实现一个算术加法操作

struct Vector2D {
    var x = 0.0, y = 0.0
}

extension Vector2D {
    static func + (left: Vector2D, right: Vector2D) -> Vector2D {
       return Vector2D(x: left.x + right.x, y: left.y + right.y)
    }
}

let vector = Vector2D(x: 3.0, y: 1.0)
let anotherVector = Vector2D(x: 2.0, y: 4.0)
let combinedVector = vector + anotherVector
// combinedVector is a Vector2D instance with values of (5.0, 5.0)

前置和后置操作

下面例子显示了一个二进制前置操作的自定义实现

extension Vector2D {
    static prefix func - (vector: Vector2D) -> Vector2D {
        return Vector2D(x: -vector.x, y: -vector.y)
    }
}

let positive = Vector2D(x: 3.0, y: 4.0)
let negative = -positive
// negative is a Vector2D instance with values of (-3.0, -4.0)
let alsoPositive = -negative
// alsoPositive is a Vector2D instance with values of (3.0, 4.0)

复合赋值操作

复合赋值操作组合赋值和另一个操作。例如,加法赋值操作(+=)组合加法和赋值操作为一个操作。你标记一个复合赋值的左输入参数类型为 inout,因为参数的值将被操作方法直接修改

下面例子实现了一个加法赋值操作

extension Vector2D {
    static func += (left: inout Vector2D, right: Vector2D) {
        left = left + right
    }
}

var original = Vector2D(x: 1.0, y: 2.0)
let vectorToAdd = Vector2D(x: 3.0, y: 4.0)
original += vectorToAdd
// original now has values of (4.0, 6.0)

注意 不能覆盖默认的赋值操作。只有复合赋值操作可被覆盖。相似的,三元操作(a ? b : c)不能覆盖

相等操作

缺省,自定义类和结构没有相等操作实现。你通常实现 == 操作,并使用 Swift 的标准库 ! = 操作的缺省实现来获得 = = 操作的反向结果。有两种实现 = = 操作的方法:你可实现你自己的,或对多数类型,你可要求 Swift 同步一个实现给你。这两种情况下,你都要遵从 Swift 标准库的 Equatable 协议

你提供一个 == 操作符的实现跟实现其他前置操作符一样

extension Vector2D: Equatable {
    static func == (left: Vector2D, right: Vector2D) -> Bool {
       return (left.x == right.x) && (left.y == right.y)
    }
}

let twoThree = Vector2D(x: 2.0, y: 3.0)
let anotherTwoThree = Vector2D(x: 2.0, y: 3.0)
if twoThree == anotherTwoThree {
    print("These two vectors are equivalent.")
}
// Prints "These two vectors are equivalent."

自定义操作符

你可声明和实现你自己自定义的操作符附加到 Swift 提供的标准操作符

在全局声明的新操作符要使用 operator 关键字,且标记 prefix、infix 或 postfix 修饰符

prefix operator +++

extension Vector2D {
    static prefix func +++ (vector: inout Vector2D) -> Vector2D {
        vector += vector
        return vector
    }
}

var toBeDoubled = Vector2D(x: 1.0, y: 4.0)
let afterDoubling = +++toBeDoubled
// toBeDoubled now has values of (2.0, 8.0)
// afterDoubling also has values of (2.0, 8.0)

自定义 Infix 操作符的优先级

自定义 infix 操作符每个属于一个优先级组。一个优先级组指明一个操作符相对其他 infix 操作符的优先级,及操作的相关性

一个自定义 infix 操作符不能直接置于给定一个缺省优先级组其优先级高于三元条件操作符的优先级的优先级组中

下面例子定义一个新的自定义 infix 操作符 +-,其属于优先级组 AdditionPrecedence

infix operator +-: AdditionPrecedence
extension Vector2D {
    static func +- (left: Vector2D, right: Vector2D) -> Vector2D {
        return Vector2D(x: left.x + right.x, y: left.y - right.y)
    }
}
let firstVector = Vector2D(x: 1.0, y: 2.0)
let secondVector = Vector2D(x: 3.0, y: 4.0)
let plusMinusVector = firstVector +- secondVector
// plusMinusVector is a Vector2D instance with values of (4.0, -2.0)

注意 你不能在定义一个 prefix 或 postfix 操作符时指定一个优先级。然而,如果你应用 prefix 和 postfix 操作符到同一个操作值上,postfix 操作符会先运行

结果构建器

一个结果构建器是一个你定义的类型,其添加创建嵌套数据的语法,比如一个列表或树,以一种自然声明式的方式。用在结果构建器中的代码可包含普通的 Swift 语法,比如 if 和 for,为处理条件和重复的数据片段

以下代码定义了一些类型来使用星和文本来画一条线

protocol Drawable {
    func draw() -> String
}
struct Line: Drawable {
    var elements: [Drawable]
    func draw() -> String {
        return elements.map { $0.draw() }.joined(separator: "")
    }
}
struct Text: Drawable {
    var content: String
    init(_ content: String) { self.content = content }
    func draw() -> String { return content }
}
struct Space: Drawable {
    func draw() -> String { return " " }
}
struct Stars: Drawable {
    var length: Int
    func draw() -> String { return String(repeating: "*", count: length) }
}
struct AllCaps: Drawable {
    var content: Drawable
    func draw() -> String { return content.draw().uppercased() }
}

let name: String? = "Ravi Patel"
let manualDrawing = Line(elements: [
     Stars(length: 3),
     Text("Hello"),
     Space(),
     AllCaps(content: Text((name ?? "World") + "!")),
     Stars(length: 2),
])
print(manualDrawing.draw())
// Prints "***Hello RAVI PATEL!**"

这个代码可以工作,但有一点不好的感觉。在 AllCaps 后深入嵌套比较晦涩。如果你需要包含 switch 或 for 循环来构建绘制的部分,则没有办法。一个结果构建器让你重写代码使得其更像 Swift 代码

为定义一个结果构建器,你写 @resultBuilder 属性到一个类型声明中。例如,下面代码定义一个结果构建器称为 DrawingBuilder,其让你使用一个声明式语法定义一个绘制

@resultBuilder
struct DrawingBuilder {
    static func buildBlock(_ components: Drawable...) -> Drawable {
        return Line(elements: components)
    }
    static func buildEither(first: Drawable) -> Drawable {
        return first
    }
    static func buildEither(second: Drawable) -> Drawable {
        return second
    }
}

DrawingBuilder 结构定义这些方法实现结果构建器语法部分。buildBlock(_:) 方法添加对在代码块中写一系列线的支持。它组合该块中组件为一条线。buildEither(first:) 和 buildEither(second:) 方法添加对 if else 的支持

你可应用 @DrawingBuilder 属性到一个函数参数,其返回一个闭包传递到方法为结果构建器为闭包创建的值,例如:

func draw(@DrawingBuilder content: () -> Drawable) -> Drawable {
    return content()
}
func caps(@DrawingBuilder content: () -> Drawable) -> Drawable {
    return AllCaps(content: content())
}

func makeGreeting(for name: String? = nil) -> Drawable {
    let greeting = draw {
        Stars(length: 3)
        Text("Hello")
        Space()
        caps {
            if let name = name {
                Text(name + "!")
            } else {
                Text("World!")
            }
        }
        Stars(length: 2)
    }
    return greeting
}
let genericGreeting = makeGreeting()
print(genericGreeting.draw())
// Prints "***Hello WORLD!**"

let personalGreeting = makeGreeting(for: "Ravi Patel")
print(personalGreeting.draw())
// Prints "***Hello RAVI PATEL!**"

makeGreeting(for:) 函数带一个 name 参数和使用它来绘制一个私人的问候。draw(_ :) 和 caps(_ :) 函数都带一个闭包作为它们的参数,并标记 @DrawingBuilder 属性。当你调用这些函数,你使用 DrawingBuilder 定义的特殊的语法。Swift 转换一个绘制的声明式描述为一系列在 DrawingBuilder 上方法的调用来构建传递到函数参数上的值。例如,Swift 转换 caps(_ :) 的调用为如下代码:

let capsDrawing = caps {
    let partialDrawing: Drawable
    if let name = name {
        let text = Text(name + "!")
        partialDrawing = DrawingBuilder.buildEither(first: text)
    } else {
        let text = Text("World!")
        partialDrawing = DrawingBuilder.buildEither(second: text)
    }
    return partialDrawing
}

Swift 转换 if else 块到调用 buildEither(first:) 和 buildEither(second:) 方法。虽然你在你的代码中不调用这些方法,显示的转换结果使得它更容易看到当你使用 DrawingBuilder 语法时 Swift 如何转换你的代码

为在特殊的绘制语法中添加写循环的支持,添加一个 buildArray(_ :) 方法

extension DrawingBuilder {
    static func buildArray(_ components: [Drawable]) -> Drawable {
        return Line(elements: components)
    }
}
let manyStars = draw {
    Text("Stars:")
    for length in 1...3 {
        Space()
        Stars(length: length)
    }
}

在上述代码中,for 循环创建了一个绘制数组,且 buildArray(_ :) 方法让该数组变成一个线

Share

Gray Code

反射二进制代码(RBC),也称为反射二进制(RB)或 在 Frank Gray 之后叫 Gray Code,是一个二进制数字系统的顺序使得两个相邻的值只有一个位不同

例如,十进制值 1 在二进制可以表示为 001 和 2 表示为 010。在 Gray code 中,这些值表示为 001 和 011。即,从 1 到 2 增加一个值只改变一个位,而不是 2 个

Gray code 广泛应用于从电子交换机中防止伪造的输出和在电子通信中加快错误矫正比如数字地面电视和一些电缆电视系统。在这些设备中 Gray code 的使用帮助简化逻辑操作和减少实际中的错误

功能

许多设备通过关闭和打开开关来显示位置。如果该设备使用自然二进制代码,3 和 4 的位置互相靠近但二进制表示的三个位数都不同

十进制 二进制
3 011
4 100

自然二进制代码的问题是物理开关不是理想的:它不太像物理开关精确同步地改变状态。上面显示的两个状态间所有三个开关改变了状态。当所有正在改变的短暂期间,开关将读取一些虚假的位置。甚至没有键反弹,短暂期可能会是 011 - 001 - 101 - 100。当开关出现在位置 001 时,观察者不能说如果有真正的位置 1,或在两个其他位置之间的一个暂时状态。如果输出反馈给一个序列系统,可能通过组合逻辑,则序列系统可能存储一个错误值

这个问题可通过一次只改变一个开关解决,这样没有任何歧义的位置,代码为一个连续集合整数,或对每个环形列表成员,一个字符信号使得没有两个代码为确定的,且每两个相邻的代码只有一个信号不同。这些代码也称为单位距离,单距离,单步,monostrophic 或 syncopic 代码,相邻代码间的 Hamming 距离为 1

发明

原理上,对于给定字节长度有多种这样的代码,但 Gray code 是第一个应用到非负整数上的一个特殊的二进制代码,二进制反射 Gray code,或 BRGC。贝尔实验室研究员 George R.Stibitz 在 1941 年用一个专利保护的应用程序描述这样的一个代码,在 1943 年获得允许。Frank Gray 在他的 1947 年专利保护的应用程序中引入反射二进制代码的名称,标记该代码“还没有识别的名字“。他从事实中获得“可能通过一些反射系统从方便的二进制代码构建“

在 Gray code 的标准编码中,最低有效位有 2 个开 2 个关的重复范型;下一个位数是 4 个开 4 个关的范型;第 i 位是 $ 2^{i} $ 开 $ 2^{i} $ 关,其他位也是这样。四个位的版本显示如下:

十进制 二进制 Gray
0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100
9 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000

对十进制 15 代码滚动到 0 只需要改变一个开关。这被称为循环或邻接属性的代码

在现代数字通信中,Gray code 在错误矫正中扮演重要的角色。例如,在数字调制方案比如 QAM 其数据典型地转换 4 位或更多符号,信号的星座表排列为位范型被相邻的星座点只一位不同来转换。通过比较前向错误矫正能矫正单位错误,它可能让接收者矫正任意由一个星座点到邻接点区域的转换错误。这使得转换系统很少会被噪音污染

尽管是 Stibitz 在 Gray 之前描述了这个代码,反射二进制代码之后被其他人命名为 Gray。两个不同的 1953 年专利保护的应用程序使用 Gray code 作为反射二进制代码的替代名;其中之一也列出“最小错误码“ 和”循环排列代码“。一个 1954 年专利保护的应用程序用了“Bell 电话 Gray code“。其他的名字包括“循环二进制代码“,”循环进度代码“,“循环排列二进制“或“循环排列的二进制“

Gray code 有时候错误认为是 19 世纪电子设备发明人 Elisha Gray

历史和实际的应用程序

数学谜

反射二进制代码在变得对工程师熟知之前应用到数学谜

二进制反射 Gray code 可表示为经典的中国环谜的底层解决方案,French Louis Gros 1872 年描述的一个序列机械谜机制

它可作为解决方案指导汉诺塔问题,基于 French Edouard Lucas 1883 年的一个游戏。相似的,Bucharest 和 Klagenfurt 塔游戏配置为三进制和八进制 Gray code

Martin Gardner 在科学美国人他的 1972 年八月数学游戏栏目中写了一个流行的 Gray code 的报道

代码也形成在超立方体上的一个汉密尔顿循环,其每个位视为一个维度

电报代码

在 1975 年或 1876 年,当法国工程师 Emile Baudot 对他的打印电报系统从使用 6 位代码改为使用 5 位代码,他在他的打印机轮上使用一个反射二进制代码排序字母,且对元音只使用 3 位代码。元音和辅音以字母序排序,且其他符号适合地排位,5 位字符码被识别为一个反射二进制代码。这个代码变成熟知的 Baudot 代码,且用一个小的改变,最终在 1932 年作为国际电报第一号(ITA1, CCITT-1)采用

同时,1874 年德国奥地利人 Otto Schaffler 展示了在维也纳使用的另一种用 5 位反射二进制代码作为相同目的的打印电报

模拟到数字信号转换

Frank Gray 因发明信号方法用来兼容彩色电视而闻名,他使用基于真空管道的一套设备发明了一种转换模拟信号到反射二进制代码组的方法。在 1947 年形成文件,该方法和设备在 1953 年获得专利权,且 Gray 的名字联系到了该代码。Gray 享有专利权的“PCM 管道“设备被贝尔实验室的 Raymond W. Sears 制作了出来。他跟 Gray 和 William M.Goodall 一起工作,他相信 Gray 在反射二进制代码上的想法

Gray 在转换模拟信号到数字信号上使用代码最小化错误上最感兴趣;他的代码在今天依然在用于这个目的

位置编码器

Gray code 相对于权重二进制编码更适合于线性和旋转位置编码器(绝对编码器和相位编码器)。这避免了当一个位置在二进制表达中多个位改变时会导致变化过程中的误读

例如,一些旋转编码器提供一个磁盘其在同心环上有电子传导 Gray code 范型。每个 track 有一个停滞的金属簧接触器提供到传导代码范型的电子接触。这些接触器一起以 Gray code 的形式产生输出信号。其他的编码器基于光纤或电磁传感器使用非接触机制产生 Gray code 输出信号

不管一个移动的编码器的机制或精度,位置测量错误可能在一些特殊位置上发生(代码边界)因为代码在它读取的特别时刻可能会改变。一个二进制输出代码可能因为在相同时刻不能使所有位改变而引起严重的位置测量错误。如果,在位置采样的时刻,一些位已改变而另一些没有,采样的位置将是不正确的。在绝对编码器中,显示位置可能远离实际的位置,且在递增编码器中,这会导致位置跟踪崩溃

相反地,位置编码器使用的 Gray code 确保任意两个连续位置的代码只有一位不同,即一个时刻只能改变一位。这样,最大位置错误将很小,显示一个位置邻接实际的位置

基因算法

由于 Gray code 的 Hamming 距离属性,它们有时使用在基因算法中。在这个领域它们非常有用,因为代码的修改允许多数时递增改变,但偶尔单个位改变可引起一个大的倾斜并导致一个新的属性

布尔电路最小化

Gray code 也用于从 1953 年开始的标签 Karnaugh 地图裁剪和 1958 年开始的 Handler 环图,这两个都是逻辑电路最小化的图像方法

错误矫正

在现代数字通信中,在应用一个错误错误矫正之前 1 维和 2 维 Gray code 在错误防止方面扮演一个重要的角色。例如,在数字调制方案比如 QAM 中数据典型地以 4 位或更多来传输,信号的星座图被排列这样位范型被邻接星座点只以一位之差覆盖。通过与能够矫正一位错误的前向错误矫正比较,对一个接收器它能够矫正导致一个星座点偏离到邻接点区域的任意传输错误。这使得传输系统不容易被噪音干扰

时钟域间的通信

数字逻辑设计师使用 Gray code 扩展通过多位统计信息同步不同时钟频率间的逻辑操作。逻辑考虑在不同时钟域上操作。它是许多不同时钟频率上操作设计大型芯片的基础

最小影响的通过状态循环

如果一个系统需要通过所有可能开关状态的一些控制组合来顺序循环,且控制的改变需要很小的花费(例如,时间、线、人工操作),一个 Gray code 最小化设置改变数来对每个状态组合只改变一个。一个例子为测试一个管道系统所有它的手工操作阀设置的组合

一个平衡 Gray code 可被构造,翻转每位相等的次数。因为位翻转分布均匀,这用下面方法优化:平衡 Gray code 最小化每个位位翻转的最大统计数

  1. Gray code 统计和算术

    George R. Stibitz 在 1941 年已经在一个二进制脉冲统计设备里利用一个反射二进制代码

    一个典型 Gray code 统计的使用是构建一个 FIFO 数据缓冲读写存在不同时钟域的端口。在这样一个双端口 FIFO 里的输入输出统计使用 Gray code 防止捕获的跨时钟域无效临时状态。当改变时更新的读写指针需要在时钟域间传递,为能跟踪每个域 FIFO 的空和满状态。指针的每个位在这个时钟域传输中是非确定性采样。这样对每个位,要么旧值要么新值被广播。因此,如果在多位指针中多个位在采样点改变,一个错误的二进制值会被广播。通过确保只改变一个位,Gray code 保证只有可能采样值为新值或旧值。典型的用 2 的指数长度的 Gray code

    有时电子系统中的数字总线用来传递一个时刻只增长或减少一个的数量,例如时钟域或一个数字模拟转换器中传递的一个事件统计输出。在这些应用程序中 Gray code 的优点是许多线广播延迟的不同呈现的代码位不能导致接收值通过超出 Gray code 顺序的状态。这个跟机械编码器构建的 Gray code 的优势相似,然而 Gray code 的源在这个例子中是一个电子统计器。统计器本身必须在 Gray code 中统计,否则如果统计器以二进制运行则统计器的输出值必须重新时钟化在它被转换为 Gray code 之后,因为当一个值从二进制转换成 Gray code,它可能在二进制数据位成为二进制到 Gray 转换电路的到达时刻不同即代码会短暂出现无序的状态。在电路转换统计值到 Gray code 之后增加一个时钟注册器可能引入一个时钟循环延迟,这样在 Gray code 中直接统计会更有利

    为产生 Gray code 统计器中的下一个统计值,它需要有一些组合逻辑增加存储的当前统计值。一个方法是增加一个 Gray code 号转换它为普通二进制代码,对一个标准二进制增加器加一,且然后转换结果为 Gray code。Gray code 统计的其他方法在 Robert W. Doran 的报告中讨论,包括在一个二进制波动统计器中从第一个主从翻转门阀中获取输出

  2. Gray code 地址

    当编程代码执行时典型地导致一个本地连续地址的指令内存访问范型,使用 Gray code 地址而不是二进制地址的总线编码可减少地址位状态改变的数量,因此在一些低电力设计中减少 CPU 能量消耗

构建一个 n 位 Gray code

n 位二进制反射 Gray code 可通过反射列表(例如,以倒序列出条目)从 n - 1 位列表中递归产生,用一个二进制 0 前置在源列表之前,用二进制 1 前置在反射列表条目之前,然后用倒序串联源列表,例如,从 n = 2 列表中产生 n = 3 列表:

2 位列表 00, 01, 11, 10
反射 10, 11, 01, 00
用 0 前置旧条目 000, 001, 011, 010
用 0 前置新条目 110, 111, 101, 100
串联 000, 001 011, 010, 110, 111, 101, 100

1 位 Gray code 是 $ G_ {1} = (0, 1) $。这可认为从一个 0 位 Gray code 包含一个 0 长度单条目 $ G_ {0} = ( \land ) $ 递归构建出来。这个从 $ G_ {n} $ 产生 $ G_ {n+1} $ 的迭代过程使得标准反射代码的如下属性更清晰:

  • $ G_ {n} $ 是数 $ 0, \ldots, 2^{n} - 1 $ 的一个排列(每个数在列表中只出现一次)
  • $ G_ {n} $ 内嵌在 $ G_ {n+1} $ 的前半段
  • 因此,编码是稳定的,一旦一个二进制数出现在 $ G_ {n} $ 中它出现在所有更长列表的相同位置;这样谈论可反射 Gray code 值 G(m) = 第 m 个反射 Gray code,从 0 开始计数
  • $ G_ {n} $ 中每个条目跟之前的条目只有一位不同(Hamming 距离为 1)
  • $ G_ {n} $ 中最后的条目跟第一个条目只有一位不同(代码可循环)

这些特性建议一个简单和快速的方法转换二进制值到对应的 Gray code。如果输入值的下一个更高位设置为 1 则每位被倒置。如果有效这可通过位移和异或操作平行处理:第 n 位 Gray code 通过计算 $ n \oplus \lfloor \frac{n}{2} \rfloor $ 来获得。前置一个 0 位代码顺序不变,前置一个 1 位反转代码顺序。如果在 i 位被倒置,邻居第 $ 2^{i} $ 块的顺序是反转的。例如,如果在 3 位代码序中 0 位被倒置,两个邻接代码序被反转

$ 000, 001, 010, 011, 100, 101, 110, 111 \to 001,000,011,010,101,100,111,110 $ (倒置 0 位)

如果第 1 位倒置,2 个代码块改变顺序:

$ 000,001,010,011,100,101,110,111 \to 010,011,000,001,110,111,100,101 $ (倒置第 1 位)

如果第 2 位倒置,4 个代码块反转顺序:

$ 000,001,010,011,100,101,110,111 \to 100,101,110,111,000,001,010,011 $ (倒置第 2 位)

这样,在位置 i 对位 $ b_ {i} $ 执行一个异或及在位置 i + 1 如果 $ b_ {i+1} = 0 $ 则对顺序不动,如果 $ b_ {i+1} = 1 $ 则反转 $ 2^{i+1} $ 代码块顺序。现在,这跟反射并前置方法产生 Gray code 的操作完全一致

一个相似的方法可用来反转转换,但每位的计算依赖下一个高位的计算值这样它不能并行执行。假设 $ g_ {i} $ 是第 i 个 Gray code 位($ g_ {0} $ 是最低位),且 $ b_ {i} $ 是第 i 个二进制代码位($ b_ {0} $ 是最低位),反转转换可递归给出:$ b_ {0} = g_ {0} $ 且 $ b_ {i} = g_ {i} \oplus b_ {i-1} $。另外,解码一个 Gray code 为一个二进制数可描述为在 Gray code 里位的一个前置和,在前置和中每个单独的累加操作用 2 取模

为迭代构建二进制反射 Gray code,在第 0 步用 $ code_ {0} = 0 $ 开始,且在第 i > 0 步找到 i 的二进制表示中最小位为 1 的位置且在之前的 $ code_ {i-1} $ 代码中在该位置翻转位来产生下一个代码 $ code_ {i} $

转换成 Gray code 和从 Gray code 转换

下面 C 函数从二进制代数和它们相关的 Gray code 之间进行转换。然而似乎有一次需要一位被处理的 Gray 到二进制的更快版本算法存在

typedef unsigned int uint;

/* This function converts an unsigned binary number to reflected binary Gray code. */
uint BinaryToGray(uint num) {
  return num ^ (num >> 1);
}

/* This function converts a reflected binary Gray code number to a binary number */
uint GrayToBinary(uint num) {
  uint mask = num;
  while (mask) {
    mask >>= 1;                 /* Each Gray code bit is exclusive-ored while all more significant bits */
    num ^= mask;
  }

  return num;
}

/* A more efficient version for Gray codes 32 bits or fewer through the use of SWAR
  (SIMD within a register) techniques.
  It implements a parallel prefix XOR function. The assignment statements can be in any order.
  This function can be adapted for longer Gray codes by adding steps */
uint GrayToBinary32(uint num) {
  num ^= num >> 16;
  num ^= num >> 8;
  num ^= num >> 4;
  num ^= num >> 2;
  num ^= num >> 1;

  return num;
}

/* A Four-bit-at-once variant changes a binary number (abcd)2 to (abcd)2 ^ (00ab)2,
   then to (abcd)2 ^ (00ab)2 ^ (0abc)2 ^ (000a)2.*/

在更新的处理器上,在解码步骤里 ALU 指令数可通过 CLMUL 指令集缩减。如果 MASK 是以一个单零数字结尾的字符为 1 的常量二进制字符串,则带灰编码的 x 用 MASK 非进位乘法将总是得到 x 或它的位对立值

Gray code 的特殊类型

在实际中,”Gray code” 总是指二进制反射 Gray code(BRGC)。然而,数学家发现了其他类型的 Gray code。像 BRGC,每个包含字节的列表,每个字节跟下一个只相差一个位(Hamming 距离为 1)

n 位 Gray code 且长度小于 $ 2^{n} $

构建 n 位二进制 Gray code 且长度小于 $ 2^{n} $,如果长度为偶数。一个可能性是用一个平衡 Gray code 开始且移除开始和结尾的值对,或在中间的。OEIS sequence A290772 给出长度为 2n 包括 0 和使用最小位数的可能的 Gray 序列

n 进制 Gray code

有许多不同于二进制反射 Gray code 的特殊类型 Gray code。其中之一为 n 进制 Gray code,也被称为非布尔 Gray code。如名称所示,这种类型 Gray code 在编码中使用非布尔值

例如,一个 3 进制 Gray code 使用值 0,1,2。(n, k) Gray code 是 k 位 n 进制 Gray code。(3,2) Gray code 元素序列为:00,01,02,12,11,10,20,21,22。(n,k) Gray code 可递归构建,跟 BRGC 相似,或可迭代构建。一个迭代产生 (N, k) Gray code 的算法如下:

/* inputs: base, digits, value
   output: Gray
   Convert a value to a Gray code with the given base and digits.
   Iterating through a sequence of values would result in a sequence
   of Gray code in which only one digit changes at a time */
void toGray(unsigned base, unsigned digits, unsigned value, unsigned gray[digits]) {
  unsigned baseN[digits];       /* store the ordinary base-N number, one digit per entry */
  unsigned i;                   /* The loop variable */

  /* Put the normal baseN number into the baseN array. For base 10, 109 would
     be stored as [9, 0, 1] */
  for (i = 0; i < digits; ++i) {
    baseN[i] = value % base;
    value = value / base;
  }

  /* Convert the normal baseN number into the Gray code equivalent.
     Note that
     the loop starts at the most significant digit and goes down */
  unsigned shift = 0;
  while (i--) {
    /* The Gray digit gets shifted down by the sum of the higher digits */
    gray[i] = (baseN[i] + shift) % base;
    shift = shift + base - gray[i]; /* Subtrace from base so shift is possible */
  }
}

// EXAMPLES
// input: value = 1899, base = 10, digits = 4
// output: baseN[] = [9,9,8,1], gray[] = [0,1,7,1]
// input: value = 1900, base = 10, digits = 4
// output: baseN[] = [0,0,9,1], gray[] = [0,1,8,1]

有一些其他的 (n, k) Gray code 的算法。从上述算法中产生的 (n, k) Gray code 也是循环的;一些算法,比如 Guan 的算法,当 k 为奇数时缺少这个属性。另一方面,这个方法一个时刻只改变一位数字,它可改变封装的值(从 n - 1 到 0 的循环)。在 Guan 的算法中,统计交替上升下降,这样两个 Gray code 之间的数字只有一位不同

Gray code 没有唯一的定义,因为这样的代码的一个列排列也是 Gray code。上述过程产生一个代码其降低低位数字,改变地越多,其更像一个正常的统计方法

看看 Skew 二进制数字系统,一个变种三进制数字系统其每次增加最多改变两个数字,每次增加可最多一个数字进位操作完成

平衡 Gray code

虽然二进制反射 Gray code 在很多场景下很有用,但在某些场景下不是最优的因为缺少“均匀”。在平衡 Cray code 中,不同坐标位置数值的改变尽可能接近。为使这更精确,设 G 为一个 R 进制完全 Gray 循环有转换序列 $ (\delta_ {k}) $;G 的转换统计(光谱)为整数的收集定义为

$ \lambda_ {k} = | { j \in \mathbb{Z}_ {R^{n}} : \delta_ {j} = k } |, \text{for} \quad k \in \mathbb{Z}_ {n} $

一个 Gray code 是均匀或均匀平衡的如果它的转换统计也是所有相等的,$ \forall k, \lambda_ {k} = \frac{R^{n}}{n} $。明显的,当 R = 2 时,只有 n 是 2 的指数倍时这样的代码才存在。否则,它可能可构建一个似平衡二进制代码,其两个转换统计之间最多只有 2 处不同;这样(组合两种情况)每个转换要么 $ 2 \lfloor \frac{2^{n}}{2n} \rfloor $ 或 $ 2 \lceil \frac{2^{n}}{2n} \rceil $。Gray code 也称为幂平衡如果所有它的转换统计相邻 2 的指数个,且这样的代码对每个 2 的指数都存在

例如,一个平衡 4 位 Gray code 有 16 个转换,可被均匀分布在所有四个位置(每个位置四个转换),使得它均匀平衡:

$ \begin{array}{llllllllllllllll} 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & 0 & \color{red}{1} & 1 & \color{red}{0} \\ 0 & 0 & \color{red}{1} & 1 & 1 & 1 & \color{red}{0} & 0 & \color{red}{1} & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & \color{red}{1} & 1 & 1 & \color{red}{0} & 0 \\ \color{red}{0} & 0 & 0 & \color{red}{1} & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 \end{array} $

一个 5 位平衡 Gray code 有总共 32 个转换,其不能均匀分布在位置上。在这个例子中,4 个位置每个有 6 个转换,且有一个位置有 8 个:

$ \begin{array}{llllllllllllllllllllllllllllllll} \color{red}{1} & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & \color{red}{1} & 1 & \color{red}{0} & 0 & 0 \\ 1 & 1 & \color{red}{0} & 0 & \color{red}{1} & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & 0 & \color{red}{1} & 1 & 1 & \color{red}{0} & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & \color{red}{1} & 1 \\ 1 & \color{red}{0} & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & \color{red}{1} \\ 1 & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & \color{red}{1} & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{1} & 1 & \color{red}{0} & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 \end{array} $

我们将展示一个似平衡二进制 Gray code 的构建和实现,其允许我们对每个 n 产生一个 n 位平衡 Gray code。主要原理是归纳构建一个 (n + 2) 位 Gray code $ G^{\prime} $ 给定一个 n 位 Gray code G 使得平衡属性被保留。为此,我们考虑分区 $ G = g_ {0}, \ldots, g_ {2^{n} - 1} $ 为偶数 L 个非空块,形如:

$ { g_ {0} }, {g_ {1}, \ldots, g_ {k_ {2}} }, {g_ {k_ {2} + 1}, \ldots, g_ {k_ {3}} }, \ldots, { g_ {k_ {L-2}+1}, \ldots, g_ {-2} }, { g_ {-1} } $

$ k_ {1} = 0, k_ {L-1} = -2, k_ {L} \equiv -1 \quad (mod \quad 2^{n}) $。这个分区引入一个 (n+2) 位 Gray code:

$ 00g_ { 0 }, $

$ 00g_ {1}, \ldots, 00g_ {k_ {2}}, 01g_ {k_ {2}}, \ldots, 01g_ {1}, 11g_ {1}, \ldots, 11g_ {k_ {2}}, $

$ 11g_ {k_ {2} + 1}, \ldots, 11g_ {k_ {3}}, 01g_ {k_ {3}}, \ldots, 01g_ {k_ {2} + 1}, 00g_ {k_ {2} +1}, \ldots, 00g_ {k_ {3}}, \ldots, $

$ 00g_ {-2}, 00g_ {-1}, 10g_{-1}, 10g_ {-2}, \ldots, 10g_ {0}, 11g_ {0}, 11g_ {-1}, 01g_ {-1}, 01g_ {0} $

如果我们定义转换重数

$ m_ {i} = | { j: \delta_ {k_ {j}} = i, 1 \le j \le L } | $

为在一个分区中连续块之间在数位 i 改变的次数,对 (n+2) 位 Gray code 通过这个分区谱 $ \lambda^{\prime}_ {i} $ 导入为

$ \lambda^{\prime}_ {i} = \left\{ \begin{array}{lc}4 \lambda_ {i}-2 m_ {i}, & \text { if } 0 \leq i < n \\ L, & \text { otherwise } \end{array} \right. $

这个构建的修饰部分为了找到一个 n 位 Gray code 的一个普适分区使得通过它引入的代码仍然是平衡的,但这只对转换重数有关;在一个位 i 转换连接两个相邻的块和在另一个 i 位上分隔块产生一个相同转换谱 $ \lambda^{\prime}_ {i} $ 上的不同的 Gray code,这样可以例如在位数 i 上指定第一个 $ m_ {i} $转换。均匀代码在 $ R \equiv 0 \quad (mod \, 4) $ 和 $ R^{n} \equiv 0 \quad (mod \, n) $ 上找到,且这个构建可扩展到 R 进制

长运行 Gray code

长运行(最大间隔)Gray code 最大化相同位置上连续改变数位的距离。即任何位的最小运行长度尽可能不改变

单调 Gray code

单调代码在互相连接网络上理论上很有用,特别对处理器的线性数列。如果我们定义一个二进制字符串的重量为字符串里 1 的个数,则虽然我们清楚 Gray code 不可能有严格的增长体重,我们可通过让代码运行在达到下一个之前估计两个相邻的重量

我们可形式化单调 Gray code 的概念如下:考虑超立方体的分区 $ Q_ {n} = (V_ {n}, E_ {n}) $ 为有相同重量的定点层级,例如

$ V_ {n}(i) = { \nu \in V_ {n} : \nu \quad \text{ has weight i } }, 0 \le i \le n $

这些层满足 $ | V_ {n}(i) | = \binom{n}{i} $。设 $ Q_ {n}(i) $ 为 $ Q_ {n} $ 引入 $ V_ {n}(i) \cup V_ {n}(i+1) $ 的子图,且设 $ E_ {n}(i) $ 为 $ Q_ {n}(i) $ 中的边。一个单调 Gray code 是 $ Q_ {n} $ 中一个哈密尔顿路径使得当 $ \delta_ {1} \in E_ {n}(i) $ 在 $ \delta_ {2} \in E_ {n}(j) $ 之前,则 $ i \le j $

一个对任意 n 的单调 n 位 Gray code 的伟大构建基于递归构建 $ 2 \binom{n}{j} $ 长度子路径 $ P_ {n, j} $ 其在 $ E_ {n}(j) $ 中有边。我们定义 $ P_ {1,0} = (0, 1), P_ {n,j} = \emptyset, j < 0 or j \ge n $ 且

$ P_ {n_1, j} = 1 P^{\pi_ {n}}_ {n,j-1}, 0P_ {n, j} $

这里,$ \pi_ {n} $ 是一个适合的被定义排列且 $ P^{\pi} $ 指路径 P 其坐标被 $ \pi $ 重新排列。这些路径导致两个单调 n 位 Gray code $ G^{(1)}_ {n}, G^{(2)}_ {n} $:

$ G^{(1)}_ {n} = P_ {n,0}P^{R}_ {n,1}P_ {n,2}P^{R}_ {n,3} \cdots, G^{(2)}_ {n} = P^{R}_ {n,0}P_ {n,1}P^{R}_ {n,2}P_ {n,3} \cdots $

$ \pi_ {n} $ 的选择确保这些代码为 Gray code 证明 $ \pi_ {n} = E^{-1}(\pi^{2}_ {n-1}) $。$ P_ {n, j} 的前几个显示在下表中

  j = 0 j = 1 j = 2 j = 3
n = 1 0, 1      
n = 2 00, 01 10, 11    
n = 3 000, 001 100, 110, 010, 011 101, 111  
n = 4 0000, 0001 1000, 1100, 0100, 0110, 0010, 0011 1010, 1011, 1001, 1101, 0101, 0111 1110, 1111

这些单调 Gray code 这样可高效实现,每个子序列元素可在 O(n) 时间复杂度下生成

单调代码有一个有趣的连接到 Lovász conjecture,其表述每个连接的定点转换图包含一个哈密尔顿路径。“中级水平”子图 $ Q_ {2n+1}(n) $ 是向量转换(即,它的自同构组是可转换的,这样每个定点有相同的“本地环境”且不能跟其他不同,因为我们可重标签坐标这样二进制数字来获得一个自同构)且在这个子图中找到一个哈密尔顿路径的问题被称为“中等层级问题“,其可提供到更一般化猜想的洞察。问对 $ n \le 15 $ 的情况题已获得肯定答复,且单调代码的后续构建确保一个至少 0.839N 长度的哈密尔顿路径,N 是中级层级子图中顶点数

Beckett-Gray code

另一种类型 Gray code,Beckett-Gray code,以爱尔兰剧作家 Samuel Beckett 命名,其在对称性上有很大的兴趣。他的剧“Quad“描写了四位演员并分割为六个时期。每个时期以一个演员进入或离开舞台结束。剧开始结束时是一个空的舞台,且 Beckette 想要演员的每个子集只出现在舞台一次。明显地当前舞台上演员的集合可呈现为 4 位二进制 Gray code。Beckette,然而,在脚本上加了另外一个限制:他希望演员进入或退出使得舞台上所在最长的演员总是存在。演员可呈现为一个先进先出队列,这样(舞台上的演员)被退出的演员总是最先入队列的。Beckette 不能找到适合他的剧的一个 Beckette Gray code,且实际上,一个完全列表所有可能的序列表明对 n = 4 没有这样的代码存在。现在知道这样的代码对 n = 2, 5, 6, 7 和 8 存在,对 n = 3 或 4 不存在。一个 8 位 Beckette-Gray code 的例子可在 Donald Knuth 的计算机编程艺术里发现。根据 Sawada 和 Wong,对 n = 6 的研究空间可被探索在 15 小时以内,且对 n = 7 的情况已发现超过 9500 种解决方案

箱中蛇代码

箱中蛇代码,或蛇,是在一个 n 维超立方体图形中包含路径的节点序列,且箱中盘代码,或盘,是在一个超立方体中包含循环的节点序列。视为 Gray code,这些序列有能检测出任意单位代码错误的属性。这种类型的代码在 1950 年末由 William H. Kautz 首次描述,之后,对一个给定超立方体维度由很多在找到最大可能代码字节数量的代码的研究

单轨 Gray code

另一种 Gray code 是由 Norman B. Spedding 开发并被 Hiltgen、Paterson 和 Brandestini 在 1996 年重定义的单轨 Gray code(STGC)。STGC 是一个长度为 n 的 P 唯一二进制编码的循环列表使得两个连续的字节只有一个位置不同,且当列表为一个 P x n 矩阵,每列是首列的一个循环位移

名称来源于他们使用的旋转编码器,轨数由联系探知,导致一个 0 或 1 的输出里的每一个结果。为减少每次在同一时刻由于不同联系不转变的噪音,一个更好的设置轨道使得联系的数据输出在 Gray code 中。为获得高尖角精确度,需要很多联系;为了达到至少 $ 1^{\circ} $ 的精确度,每个旋转需要至少 360 个不同的位置,需要一个至少 9 位的数据,且相同数量的联系

如果所有联系位于相同尖角位置,则需要 9 个轨来获得一个至少 $ 1^{ \circ } $ 的标准 BRGC 精确度。然而,如果制造商移动一个联系到一个不同尖角位置(但跟中心轴相同距离),则对应“环范型”需要被旋转相同的角度来获得相同的输出。如果最高有效位足够旋转,它精确匹配下一个环输出。因为两个环唯一确定,内环可移掉,且该环传感器移动到剩下的唯一确认的环上(但从其他传感器在那个角度在该环上)。单环上这两个传感器产生一个四边形编码器。它缩减一个 $ 1^{\circ} $ 解决方案角度编码器的轨道数为 8 个。更进一步缩减轨道数不能在 BRGC 上实现

多年来,Torsten Sillke 和其他数学家相信在单轨上不可能加密位置这样连续位置上只有一个传感器不同,除了 2-传感器,1 轨四边形编码器。这样对应用程序 8 个轨道太笨重,人们使用单轨递增编码器(四边形编码器)或 2-轨“四边形编码器+引用孔“编码器

Norman B. Spedding 在 1994 年注册了一个专利权用几个例子显示这是可能的。虽然它不可能在单轨上用 n 个传感器区分 $ 2^{n} $ 个位置,它可能区分接近该数的数目。Etzion 和 Peterson 推测当 n 是 2 的指数时,n 个传感器可区分最多 $ 2^{n} - 2n $ 个位置且对质数 n 限制是 $ 2^{n} -2 $ 个位置。作者继续产生一个长度为 9 的 504 位置单轨代码,他们相信是优化的。因为这个数比 $ 2^{8} = 256 $ 大,任意代码需要超过 8 个传感器,虽然一个 BRGC 用 9 个传感器可区分 512 个位置

对 P = 30 和 n = 5 的一个 STGC 重生成如下

角度 代码 角度 代码 角度 代码 角度 代码 角度 代码
0 10000 72 01000 144 00100 216 00010 288 00001
12 10100 84 01010 156 00101 228 10010 300 01001
24 11100 96 01110 168 00111 240 10011 312 11001
36 11110 108 01111 180 10111 252 11011 324 11101
48 11010 120 01101 192 10110 264 01001 336 10101
60 11000 132 01100 204 00110 276 00011 348 10001

每列是首列的一个循环位移,且从任意行到下一行只有一位改变。单轨自然是有用的在这些轮子的制造上(相比 BRGC),因只有一个轨需要,这样缩减了他们的成本和大小。Gray code 自然是有用的(相比较链代码,也称为 De Bruijn 序列),因为只有一个传感器在一个时刻改变,这样两个连续状态之间只有一个增或减角度单元在转换期间设备的测量可以得到解决

因为这个 30 度的例子已添加,在更高角度解决方案的例子上有很多有趣的地方。在 2008 年,Gary Williams,基于之前的工作发现一个 9 位单轨 Gray code 给出一个 1 度的解决方案。这个 Gray code 用于设计一个实际的设备发布在网站 Thingverse 上。这个设备在 2022 年 7 月被 etzenseep(Florian Bauer)设计

一个 P = 360 且 n = 9 的 STGC 重生成如下:

角度 代码 角度 代码 角度 代码 角度 代码 角度 代码 角度 代码 角度 代码 角度 代码 角度 代码
0 100000001 40 000000011 80 000000110 120 000001100 160 000011000 200 000110000 240 001100000 280 011000000 320 110000000
1 110000001 41 100000011 81 000000111 121 000001110 161 000011100 201 000111000 241 001110000 281 011100000 321 111000000
2 111000001 42 110000011 82 100000111 122 000001111 162 000011110 202 000111100 242 001111000 282 011110000 322 111100000
3 111000011 43 110000111 83 100001111 123 000011111 163 000111110 203 001111100 243 011111000 283 111110000 323 111100001
4 111000111 44 110001111 84 100011111 124 000111111 164 001111110 204 011111100 244 111111000 284 111110001 324 111100011
5 111001111 45 110011111 85 100111111 125 001111111 165 011111110 205 111111100 245 111111001 285 111110011 325 111100111
6 111011111 46 110111111 86 101111111 126 011111111 166 111111110 206 111111101 246 111111011 286 111110111 326 111101111
7 111011011 47 110110111 87 101101111 127 011011111 167 110111110 207 101111101 247 011111011 287 111110110 327 111101101
8 101011011 48 010110111 88 101101110 128 011011101 168 110111010 208 101110101 248 011101011 288 111010110 328 110101101
9 101011111 49 010111111 89 101111110 129 011111101 169 111111010 209 111110101 249 111101011 289 111010111 329 110101111
10 101011101 50 010111011 90 101110110 130 011101101 170 111011010 210 110110101 250 101101011 290 011010111 330 110101110
11 101010101 51 010101011 91 101010110 131 010101101 171 101011010 211 010110101 251 101101010 291 011010101 331 110101010
12 101010111 52 010101111 92 101011110 132 010111101 172 101111010 212 011110101 252 111101010 292 111010101 332 110101011
13 101110111 53 011101111 93 111011110 133 110111101 173 101111011 213 011110111 253 111101110 293 111011101 333 110111011
14 001110111 54 011101110 94 111011100 134 110111001 174 101110011 214 011100111 254 111001110 294 110011101 334 100111011
15 001010111 55 010101110 95 101011100 135 010111001 175 101110010 215 011100101 255 111001010 295 110010101 335 100101011
16 001011111 56 010111110 96 101111100 136 011111001 176 111110010 216 111100101 256 111001011 296 110010111 336 100101111
17 001011011 57 010110110 97 101101100 137 011011001 177 110110010 217 101100101 257 011001011 297 110010110 337 100101101
18 001011001 58 010110010 98 101100100 138 011001001 178 110010010 218 100100101 258 001001011 298 010010110 338 100101100
19 001111001 59 011110010 99 111100100 139 111001001 179 110010011 219 100100111 259 001001111 299 010011110 339 100111100
20 001111101 60 011111010 100 111110100 140 111101001 180 111010011 220 110100111 260 101001111 300 010011111 340 100111110
21 000111101 61 001111010 101 011110100 141 111101000 181 111010001 221 110100011 261 101000111 301 010001111 341 100011110
22 000110101 62 001101010 102 011010100 142 110101000 182 101010001 222 010100011 262 101000110 302 010001101 342 100011010
23 000100101 63 001001010 103 010010100 143 100101000 183 001010001 223 010100010 263 101000100 303 010001001 343 100010010
24 000101101 64 001011010 104 010110100 144 101101000 184 011010001 224 110100010 264 101000101 304 010001011 344 100010110
25 000101001 65 001010010 105 010100100 145 101001000 185 010010001 225 100100010 265 001000101 305 010001010 345 100010100
26 000111001 66 001110010 106 011100100 146 111001000 186 110010001 226 100100011 266 001000111 306 010001110 346 100011100
27 000110001 67 001100010 107 011000100 147 110001000 187 100010001 227 000100011 267 001000110 307 010001100 347 100011000
28 000010001 68 000100010 108 001000100 148 010001000 188 100010000 228 000100001 268 001000010 308 010000100 348 100001000
29 000011001 69 000110010 109 001100100 149 011001000 189 110010000 229 100100001 269 001000011 309 010000110 349 100001100
30 000001001 70 000010010 110 000100100 150 001001000 190 010010000 230 100100000 270 001000001 310 010000010 350 100000100
31 100001001 71 000010011 111 000100110 151 001001100 191 010011000 231 100110000 271 001100001 311 011000010 351 110000100
32 100001101 72 000011011 112 000110110 152 001101100 192 011011000 232 110110000 272 101100001 312 011000011 352 110000110
33 100000101 73 000001011 113 000010110 153 000101100 193 001011000 233 010110000 273 101100000 313 011000001 353 110000010
34 110000101 74 100001011 114 000010111 154 000101110 194 001011100 234 010111000 274 101110000 314 011100001 354 111000010
35 010000101 75 100001010 115 000010101 155 000101010 195 001010100 235 010101000 275 101010000 315 010100001 355 101000010
36 010000111 76 100001110 116 000011101 156 000111010 196 001110100 236 011101000 276 111010000 316 110100001 356 101000011
37 010000011 77 100000110 117 000001101 157 000011010 197 000110100 237 001101000 277 011010000 317 110100000 357 101000001
38 010000001 78 100000010 118 000000101 158 000001010 198 000010100 238 000101000 278 001010000 318 010100000 358 101000000
39 000000001 79 000000010 119 000000100 159 000001000 199 000010000 239 000100000 279 001000000 319 010000000 359 100000000

对 9 个传感器已 40 度分割的单轨 Gray code 的 20 个轨道的开始和结束角度

开始角度 结束角度 长度
3 4 2
23 28 6
31 37 7
44 48 5
56 60 5
64 71 8
74 76 3
88 91 4
94 96 3
99 104 6
110 115 6
131 134 4
138 154 17
173 181 9
186 187 2
220 238 19
242 246 5
273 279 7
286 289 4
307 360 54

两维 Gray code

两维 Gray code 用在通信上星座的正交幅度调制(QAM)邻接点上最小化位错误数量。在一个典型的一个位不同的编码水平和垂直邻接星座点,和 2 位不同的对焦邻接点

两维 Gray code 也用在位置确定方案上,代码应用于区域地图比如地球表面的墨卡托投影法和一个适合的两维距离函数比如曼海姆度量用来计算两个编码位置的距离,因此组合了 Hamming 距离及循环连续的墨卡托投影法的特性

过量 Gray code

如果一个特殊代码值的子段从该值中提取,例如一个 4 位 Gray code 的最后 3 位,结果代码为一个过量的 Gray code。这个代码显示如果原始值进一步增加这些提取位的统计回退属性。这个原因是 Gray 编码的值不显示溢出属性,从经典的二进制编码,当增加过最高值

例如:Gray code 的最高 3 位,7, 编码为 (0)100。添加 1 结果为 8,编码到 Gray code 为 1100。最后 3 位不溢出且如果你进一步增加原来的 4 位代码统计也回归

当与传感器工作在一个系列输出多个 Gray 编码值,应该注意是否传感器产生这些值编码在单个 Gray code 或作为独立的,否则值可能当期望溢出时出现统计回归

Gray 等距映射

双射 $ \{ 0 \leftrightarrow 00, 1 \leftrightarrow 01, 2 \leftrightarrow 11, 3 \leftrightarrow 10 \} $ 在由 Hamming 距离给定的度量上的有限域 $ \mathbb{Z}^{2}_ {2} $ 上的度量空间与 Lee 距离给定的度量上的有限环 $ \mathbb{Z}_ {4} $ 上的度量空间之间确立了一个等距映射。映射可扩展到一个 Hamming 空间 $ \mathbb{Z}^{2m}_ {2} $ 和 $ \mathbb{Z}^{m}_ {4} $ 上的一个等距映射。它的重要性依赖于确定一个在各种好的但不必须的线性代码比如在 $ \mathbb{Z}_ {4} $ 上环线性代码在 $ \mathbb{Z}^{2}_ {2} $ 上的 Gray 映射的像