Frage zur Programmierung eines Prüfbitgenerator

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
__blackjack__
User
Beiträge: 14030
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Wobei der hier ja eigentlich auch nicht wirklich kompliziert ist. Das wiederholt sich im Grunde ja bloss für jedes Bit im Mittelteil. Man kann den Graph in der Mitte aufteilen, wobei links die Zustände für Prüfbit = 0 sind und rechts die Zustände für Prüfbit = 1 und dann braucht man halt für jedes Bit die beiden Varianten das die Eingabe 0 oder 1 ist und wieder die gleiche Ausgabe ergeben muss. Wenn die Eingabe 0 ist, bleibt man in der gleichen Häfte, wenn sie 1 ist, wechselt man in die andere Hälfte, weil sich damit die Anzahl der 1en und damit das Prüfbit ändert.

Da könnte man durch ein bisschen Nachdenken drauf kommen. Wobei ich ja schon zugegeben habe, das mir die Erklärung erst nachträglich beim betrachten des Graphen wie Schuppen von den Augen gefallen ist.

Der Graph ist durch die Überlegung entstanden, dass ein Zustand durch die Eingabe zu maximal zwei Folgezuständen führen kann, und das bei 7 Eingaben maximal ein Baum mit 127 Knoten entsteht. Man kann davon aber Knoten zusammenfassen, da ein Zustand beschrieben werden kann aus der Bitnummer 0 bis 8 (0 = noch kein Bit eingegeben = Startzustand), der Ausgabe die gemacht werden muss (0 oder 1), und dem Prüfbitwert bis dahin (0 oder 1). Das ganze habe ich Kotlin programmiert. Das Programm spuckt den Quelltext im Graphviz-Format aus, mit dem die Grafik erstellt wurde:

Code: Alles auswählen

package de.python_forum.blackjack

data class State (
        val bitNumber: Int = 0,
        val output: String = "",
        val parity: Boolean = false
) : Comparable<State> {
    fun nextLevel(bit: Boolean) = this.copy(
            bitNumber = bitNumber + 1,
            output = if (bit) "1" else "0",
            parity = parity xor bit
    )

    fun parityOutputState() = this.copy(
            bitNumber = bitNumber + 1,
            output = if (parity) "1" else "0"
    )

    override fun compareTo(other: State) = when {
        bitNumber != other.bitNumber -> bitNumber - other.bitNumber
        output != other.output -> output.compareTo(other.output)
        else -> parity.compareTo(other.parity)
    }
}

class Node(val state: State) : Comparable<Node> {
    private val _id = nextId++
    private val _children = HashMap<String, Node>()
    val id: String
        get() = "n$_id"
    val children: Iterable<Map.Entry<String, Node>>
        get() = _children.asIterable()

    fun add(input: String, node: Node) {
        _children[input] = node
    }

    override fun compareTo(other: Node): Int = state.compareTo(other.state)

    companion object {
        private var nextId: Int = 0
    }
}

class Graph(start: State) {
    private val stateToNode = HashMap<State, Node>()
    val nodes: Iterable<Node>
        get() = stateToNode.values

    init {
        stateToNode[start] = Node(start)
    }

    fun get(state: State) = stateToNode.computeIfAbsent(state, ::Node)

    fun connect(stateA: State, stateB: State, input: String) {
        get(stateA).add(input, get(stateB))
    }
}

fun buildNodes(bitCount: Int): Iterable<Node> {
    val startState = State()
    val graph = Graph(startState)
    var level = listOf(startState)

    repeat(bitCount) {
        val nextLevel = ArrayList<State>(level.size * 2)
        for (state in level) {
            for (bit in arrayOf(false, true)) {
                val nextState = state.nextLevel(bit)
                nextLevel.add(nextState)
                graph.connect(state, nextState, if (bit) "1" else "0")
            }
        }
        level = nextLevel
    }
    for (state in level.toSet()) {
        graph.connect(state, state.parityOutputState(), "")
    }
    return graph.nodes
}

private fun printNode(node: Node) {
    println("  ${node.id} [label=\"${node.state.output}\"];")
}

private fun printEdges(node: Node) {
    for ((edge, child) in node.children) {
        println("  ${node.id} -> ${child.id}" +
                " [label=\"${if (edge.isEmpty()) "ε" else edge}\"]")
    }
}

fun printGraphviz(nodes: Iterable<Node>) {
    val sortedNodes = nodes.sorted()
    println("digraph {")
    sortedNodes.forEach(::printNode)
    sortedNodes.forEach(::printEdges)
    println("}")
}

fun main() {
    printGraphviz(buildNodes(7))
}
„A life is like a garden. Perfect moments can be had, but not preserved, except in memory. LLAP” — Leonard Nimoy's last tweet.
Antworten