方案 - 全加器输出格式
Scheme - Full adder output format
所以我现在几乎完成了整个作业，但是有 1 个问题让我感到困惑（尽管我觉得答案真的很简单）。
问题 3.5:
编写一个程序将您的结果转换为所需的输出格式。
预期输出和格式如下：
((0) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
((0) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
((1) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0)
((1) 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0)
((1) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)
((0) 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1)
其中，第一个元素是加法的进位。如果进位输出为 (1)，则表示加法器发生溢出。列表的其余元素是总和。
现在我得到的输出是这样的：
(0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0)
(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0)
(1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)
(0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1)
有谁知道我怎样才能正确格式化它？我一直在想，不知道该怎么办。
编辑-
这是生成输出的代码：
(define binaryadd (lambda(L1 L2)
(let ((len1 (length L1)) (len2 (length L2)))
(if (> len1 len2)
(binaryadd L2 L1)
(if (< len1 len2)
(binaryadd (append '(0) L1) L2)
(recursiveAdd (append '(0) L1) (append '(0) L2) 0)
)) ) ))
(define recursiveAdd (lambda(L1 L2 carry)
(if (null? L1)
'()
(let ((t (+ (tail L1) (tail L2) carry)))
(append (recursiveAdd (rmtail L1)
(rmtail L2)
(quotient t 2))
(list (remainder t 2))
)) ) ) )
(define n-bit-adder (lambda(A B n)
(binaryAdd A B)
))
(define X1 '(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) )
(define X2 '(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) )
(define X3 '(0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1) )
(define X4 '(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0) )
(define X5 '(0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1) )
(define X6 '(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1) )
(n-bit-adder X1 X2 32)
(n-bit-adder X3 X4 32)
(n-bit-adder X5 X6 32)
(n-bit-adder X2 X3 32)
(n-bit-adder X4 X5 32)
(n-bit-adder X1 X6 32)
让我们做一个full adder:
#lang racket
(define (adder-output S Cout)
(hash 'S S
'Cout Cout))
;; bit bit bit -> bit bit
;; A B Cin -> S Cout
(define (full-adder inputs)
(match (hash-values inputs)
['(0 0 0) (adder-output 0 0)]
['(1 0 0) (adder-output 1 0)]
['(0 1 0) (adder-output 1 0)]
['(0 0 1) (adder-output 1 0)]
['(1 1 0) (adder-output 0 1)]
['(1 0 1) (adder-output 0 1)]
['(0 1 1) (adder-output 0 1)]
['(1 1 1) (adder-output 1 1)]
[ _ (error "binary-adder: bad input")]))
也许可以为它写一些测试：
(module+ test
(require rackunit
rackunit/text-ui)
(define bit-values '(0 1))
(define inputs
(map
(lambda (x)
(hash 'A (first x)
'B (second x)
'Cin (third x)))
(for*/list ([A bit-values]
[B bit-values]
[Cin bit-values])
(list A B Cin))))
(define outputs
(map (lambda (x)
(hash 'S (first x)
'Cout (second x)))
'((0 0)
(1 0)
(1 0)
(0 1)
(1 0)
(0 1)
(0 1)
(1 1))))
(define (unit-test in out)
(check-equal? (full-adder in)
out))
(define (test-harness ins outs)
(if (or (null? ins)
(null? outs))
'test-complete
(begin
(unit-test (first ins)
(first outs))
(test-harness (rest ins)
(rest outs)))))
(define-test-suite
full-adder-tests
(test-harness inputs outputs))
(run-tests full-adder-tests))
既然一切正常，我们只需将全加器串成一个 ripple-carry-adder with a recursive interior definition utilizing a trampoline and turning the big-bit-endinian 值到小位字节序值，这样更容易对输出进行 cons。
(define (ripple-adder value1 value2)
(define v1 (reverse value1))
(define v2 (reverse value2))
(define (add v1 v2 previous-result output)
(define carry-bit (hash-ref previous-result 'Cout))
(define out-bit (hash-ref previous-result 'S))
(if (or (null? v1)
(null? v2))
(cons (list carry-bit) (cons out-bit output))
(let
([next-add-input
(hash 'A (first v1)
'B (first v2)
'Cin carry-bit)])
(add (rest v1)
(rest v2)
(full-adder next-add-input)
(cons out-bit output)))))
(add (rest v1)
(rest v2)
(full-adder (hash 'A (first v1)
'B (first v2)
'Cin 0 ))
null))
那么如果这些测试有效：
(module+ test
(define-test-suite
ripple-adder-tests
(test-equal?
"two bit 0 + 0"
(ripple-adder '(0 0) '(0 0))
'((0) 0 0))
(test-equal?
"three bit 0 + 0"
(ripple-adder '(0 0 0) '(0 0 0))
'((0) 0 0 0))
(test-equal?
"three bit 1 + 0"
(ripple-adder '(0 0 1) '(0 0 0))
'((0) 0 0 1))
(test-equal?
"two bit 1 + 1"
(ripple-adder '(0 1) '(0 1))
'((0) 1 0))
(test-equal?
"two bit 2 + 2"
(ripple-adder '(1 0) '(1 0))
'((1) 0 0)))
(test-equal?
"three bit 2 + 2"
(ripple-adder '(0 1 0) '(0 1 0))
'((0) 1 0 0))
(run-tests ripple-adder-tests))
我们可能会冒险将其作为家庭作业上交。当然要遵守学术诚信要求。
以防您仍然需要一个全加器以及它的其余部分，这将产生您需要的输出。您需要一种方法来反转列表。检查下面代码中的最后一个过程 reverseList。
硬件代码使用请谨慎
(define and-gate
(lambda (a b)
(if (= a b 1)
1
0)))
(and-gate 0 0)
(and-gate 0 1)
(and-gate 1 0)
(and-gate 1 1)
(newline)
(define (or-gate a b)
(if (not (= 0 (+ a b)))
1
0))
(or-gate 0 0)
(or-gate 0 1)
(or-gate 1 0)
(or-gate 1 1)
(newline)
(define xor-gate
(lambda (a b)
(if (= a b)
0
1)))
(xor-gate 0 0)
(xor-gate 0 1)
(xor-gate 1 0)
(xor-gate 1 1)
(newline)
(define (bitAdder x a b)
(cons (sum-bit x a b)
(carry-out x a b)))
(define (sum-bit x a b)
(xor-gate x (xor-gate a b)))
(define (carry-out x a b)
(or-gate (and-gate a b)
(or-gate (and-gate x a)
(and-gate x b))))
(bitAdder 0 0 0)
(bitAdder 0 0 1)
(bitAdder 0 1 0)
(bitAdder 0 1 1)
(bitAdder 1 0 0)
(bitAdder 1 0 1)
(bitAdder 1 1 0)
(bitAdder 1 1 1)
(newline)
(define (tail lst)
(if (null? (cdr lst))
(car lst)
(tail (cdr lst))))
(define (rmtail lst)
(if (null? (cdr lst))
'()
(cons (car lst)
(rmtail (cdr lst)))))
(define (recursiveAdd a b c)
(if (null? a)
(list (list c))
(cons (car (bitAdder (tail a) (tail b) c))
(recursiveAdd (rmtail a) (rmtail b) (cdr (bitAdder (tail a) (tail b) c))))))
(define (n-bit-adder a b n)
(reverseList (recursiveAdd a b 0)))
(define (reverseList lst)
(if (null? lst)
'()
(append (reverseList (cdr lst)) (list (car lst)))))
;; Test cases
(define X1 '(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) )
(define X2 '(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) )
(define X3 '(0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1) )
(define X4 '(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0) )
(define X5 '(0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1) )
(define X6 '(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1) )
(n-bit-adder X1 X2 32)
(n-bit-adder X3 X4 32)
(n-bit-adder X5 X6 32)
(n-bit-adder X2 X3 32)
(n-bit-adder X4 X5 32)
(n-bit-adder X1 X6 32)
输出： （应符合您的预期输出）
((0) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
((0) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
((1) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0)
((1) 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0)
((1) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)
((0) 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1)
所以我现在几乎完成了整个作业，但是有 1 个问题让我感到困惑（尽管我觉得答案真的很简单）。
问题 3.5:
编写一个程序将您的结果转换为所需的输出格式。
预期输出和格式如下：
((0) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
((0) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
((1) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0)
((1) 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0)
((1) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)
((0) 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1)
其中，第一个元素是加法的进位。如果进位输出为 (1)，则表示加法器发生溢出。列表的其余元素是总和。
现在我得到的输出是这样的：
(0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0)
(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0)
(1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)
(0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1)
有谁知道我怎样才能正确格式化它？我一直在想，不知道该怎么办。
编辑-
这是生成输出的代码：
(define binaryadd (lambda(L1 L2)
(let ((len1 (length L1)) (len2 (length L2)))
(if (> len1 len2)
(binaryadd L2 L1)
(if (< len1 len2)
(binaryadd (append '(0) L1) L2)
(recursiveAdd (append '(0) L1) (append '(0) L2) 0)
)) ) ))
(define recursiveAdd (lambda(L1 L2 carry)
(if (null? L1)
'()
(let ((t (+ (tail L1) (tail L2) carry)))
(append (recursiveAdd (rmtail L1)
(rmtail L2)
(quotient t 2))
(list (remainder t 2))
)) ) ) )
(define n-bit-adder (lambda(A B n)
(binaryAdd A B)
))
(define X1 '(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) )
(define X2 '(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) )
(define X3 '(0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1) )
(define X4 '(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0) )
(define X5 '(0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1) )
(define X6 '(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1) )
(n-bit-adder X1 X2 32)
(n-bit-adder X3 X4 32)
(n-bit-adder X5 X6 32)
(n-bit-adder X2 X3 32)
(n-bit-adder X4 X5 32)
(n-bit-adder X1 X6 32)
让我们做一个full adder:
#lang racket
(define (adder-output S Cout)
(hash 'S S
'Cout Cout))
;; bit bit bit -> bit bit
;; A B Cin -> S Cout
(define (full-adder inputs)
(match (hash-values inputs)
['(0 0 0) (adder-output 0 0)]
['(1 0 0) (adder-output 1 0)]
['(0 1 0) (adder-output 1 0)]
['(0 0 1) (adder-output 1 0)]
['(1 1 0) (adder-output 0 1)]
['(1 0 1) (adder-output 0 1)]
['(0 1 1) (adder-output 0 1)]
['(1 1 1) (adder-output 1 1)]
[ _ (error "binary-adder: bad input")]))
也许可以为它写一些测试：
(module+ test
(require rackunit
rackunit/text-ui)
(define bit-values '(0 1))
(define inputs
(map
(lambda (x)
(hash 'A (first x)
'B (second x)
'Cin (third x)))
(for*/list ([A bit-values]
[B bit-values]
[Cin bit-values])
(list A B Cin))))
(define outputs
(map (lambda (x)
(hash 'S (first x)
'Cout (second x)))
'((0 0)
(1 0)
(1 0)
(0 1)
(1 0)
(0 1)
(0 1)
(1 1))))
(define (unit-test in out)
(check-equal? (full-adder in)
out))
(define (test-harness ins outs)
(if (or (null? ins)
(null? outs))
'test-complete
(begin
(unit-test (first ins)
(first outs))
(test-harness (rest ins)
(rest outs)))))
(define-test-suite
full-adder-tests
(test-harness inputs outputs))
(run-tests full-adder-tests))
既然一切正常，我们只需将全加器串成一个 ripple-carry-adder with a recursive interior definition utilizing a trampoline and turning the big-bit-endinian 值到小位字节序值，这样更容易对输出进行 cons。
(define (ripple-adder value1 value2)
(define v1 (reverse value1))
(define v2 (reverse value2))
(define (add v1 v2 previous-result output)
(define carry-bit (hash-ref previous-result 'Cout))
(define out-bit (hash-ref previous-result 'S))
(if (or (null? v1)
(null? v2))
(cons (list carry-bit) (cons out-bit output))
(let
([next-add-input
(hash 'A (first v1)
'B (first v2)
'Cin carry-bit)])
(add (rest v1)
(rest v2)
(full-adder next-add-input)
(cons out-bit output)))))
(add (rest v1)
(rest v2)
(full-adder (hash 'A (first v1)
'B (first v2)
'Cin 0 ))
null))
那么如果这些测试有效：
(module+ test
(define-test-suite
ripple-adder-tests
(test-equal?
"two bit 0 + 0"
(ripple-adder '(0 0) '(0 0))
'((0) 0 0))
(test-equal?
"three bit 0 + 0"
(ripple-adder '(0 0 0) '(0 0 0))
'((0) 0 0 0))
(test-equal?
"three bit 1 + 0"
(ripple-adder '(0 0 1) '(0 0 0))
'((0) 0 0 1))
(test-equal?
"two bit 1 + 1"
(ripple-adder '(0 1) '(0 1))
'((0) 1 0))
(test-equal?
"two bit 2 + 2"
(ripple-adder '(1 0) '(1 0))
'((1) 0 0)))
(test-equal?
"three bit 2 + 2"
(ripple-adder '(0 1 0) '(0 1 0))
'((0) 1 0 0))
(run-tests ripple-adder-tests))
我们可能会冒险将其作为家庭作业上交。当然要遵守学术诚信要求。
以防您仍然需要一个全加器以及它的其余部分，这将产生您需要的输出。您需要一种方法来反转列表。检查下面代码中的最后一个过程 reverseList。
硬件代码使用请谨慎
(define and-gate
(lambda (a b)
(if (= a b 1)
1
0)))
(and-gate 0 0)
(and-gate 0 1)
(and-gate 1 0)
(and-gate 1 1)
(newline)
(define (or-gate a b)
(if (not (= 0 (+ a b)))
1
0))
(or-gate 0 0)
(or-gate 0 1)
(or-gate 1 0)
(or-gate 1 1)
(newline)
(define xor-gate
(lambda (a b)
(if (= a b)
0
1)))
(xor-gate 0 0)
(xor-gate 0 1)
(xor-gate 1 0)
(xor-gate 1 1)
(newline)
(define (bitAdder x a b)
(cons (sum-bit x a b)
(carry-out x a b)))
(define (sum-bit x a b)
(xor-gate x (xor-gate a b)))
(define (carry-out x a b)
(or-gate (and-gate a b)
(or-gate (and-gate x a)
(and-gate x b))))
(bitAdder 0 0 0)
(bitAdder 0 0 1)
(bitAdder 0 1 0)
(bitAdder 0 1 1)
(bitAdder 1 0 0)
(bitAdder 1 0 1)
(bitAdder 1 1 0)
(bitAdder 1 1 1)
(newline)
(define (tail lst)
(if (null? (cdr lst))
(car lst)
(tail (cdr lst))))
(define (rmtail lst)
(if (null? (cdr lst))
'()
(cons (car lst)
(rmtail (cdr lst)))))
(define (recursiveAdd a b c)
(if (null? a)
(list (list c))
(cons (car (bitAdder (tail a) (tail b) c))
(recursiveAdd (rmtail a) (rmtail b) (cdr (bitAdder (tail a) (tail b) c))))))
(define (n-bit-adder a b n)
(reverseList (recursiveAdd a b 0)))
(define (reverseList lst)
(if (null? lst)
'()
(append (reverseList (cdr lst)) (list (car lst)))))
;; Test cases
(define X1 '(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) )
(define X2 '(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) )
(define X3 '(0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1) )
(define X4 '(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0) )
(define X5 '(0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1) )
(define X6 '(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1) )
(n-bit-adder X1 X2 32)
(n-bit-adder X3 X4 32)
(n-bit-adder X5 X6 32)
(n-bit-adder X2 X3 32)
(n-bit-adder X4 X5 32)
(n-bit-adder X1 X6 32)
输出： （应符合您的预期输出）
((0) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
((0) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
((1) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0)
((1) 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0)
((1) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)
((0) 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1)