RFC70 日本語訳

0070 Note on Padding. S.D. Crocker. October 1970. (Format: TXT=12790 bytes) (Updated by RFC0228) (Status: UNKNOWN)
プログラムでの自動翻訳です。
RFC一覧
英語原文

Network Working Group                                      S. Crocker
Request for Comments #70                                   UCLA
                                                           15 October 70

コメント#70UCLA1970年10月15日を求めるネットワークワーキンググループS.医者要求

                           A Note on Padding

詰め物に関する注

The padding on a message is a string of the form 10*.  For Hosts with
word lengths 16, 32, 48, etc., bits long, this string is necessarily in
the last word received from the Imp.  For Hosts with word lengths which
are not a multiple of 16 (but which are at least 16 bits long), the 1
bit will be in either the last word or the next to last word.  Of
course if the 1 bit is in the next to last word, the last word is all
zero.

メッセージにおける詰め物はフォーム10*のストリングです。語長16、32、48などがあるHosts、長い何ビットも、このストリングは必ずImpから受け取られた締め括りの言葉にあります。 16(しかし、長さ少なくとも16ビットである)の倍数でない語長があるHostsに関しては、1ビットが最後に言い表す締め括りの言葉か次のどちらかにあるでしょう。 もちろん、1ビットが最後に言い表す次にあるなら、締め括りの言葉はすべてゼロです。

An unpleasant coding task is discovering the bit position of the 1 bit
within its word.  One obvious technique is to repeatedly test the
low-order bit, shifting the word right one bit position if the
low-order bit is zero.  The following techniques are more pleasant.

不快なコード化タスクは単語の中で1ビットのビット位置を発見することです。 1つの明白なテクニックは繰り返して下位のビットをテストすることです、まさしく1つが下位のビットがゼロであるなら位置に噛み付いたという単語を移行させて。 以下のテクニックは、より快いです。

Isolating the Low-Order Bit

下位のビットを隔離します。

Let W be a non-zero word, where the word length is n.  Then W is of the
form

Wが非ゼロ単語であることをさせてください。そこでは、語長がnです。 そして、Wはフォームのものです。

            x....x10....0
            \__ __/\__ __/
               V      V
             n-k-1    k

x.…x10…0 \__ __/\__ __/ V V n-k-1 k

where 0<=k<n

どこk0<=<n

and the x's are arbitrary bits.

そして、xのものは任意のビットです。

Assuming two's complement arithmetic,

2の補数演算を仮定します。

            W-1    =       x....x01....1
                           _    _
             -W    =       x....x10....0
              _            _    _
              W    =       x....x01....1

W-1はx.と等しいです…x01…1_ _-Wはx.と等しいです…x10…0_ _ _Wはx.と等しいです…x01…1

By using AND, OR and exclusive OR with various pairs of these
quantities, useful new forms are obtained.

これらの量の様々な組と共にAND、OR、および排他的論理和を使用することによって、役に立つ新しいフォームを得ます。

For example,

例えば

                                                                [Page 1]

Network Working Group      A Note on Padding                      RFC 70

[1ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。

            W AND W-1       xx...x00....0
                           \__ __/\__ __/
                              V      V
                            n-k-1    k

W AND W-1 xx…x00…0 \__ __/\__ __/ V V n-k-1 k

thus removing the low-order 1 bit;

その結果、下位を1ビット取り除きます。

also W AND -W =           0....010....0
                         __ __/__ __/
                            V      V
                          n-k-1    k

Wとも-W=0…010....0 __ __/__ __/V V n-k-1k

thus isolating the low-order bit.

その結果、下位のビットを隔離します。

Below, we will focus solely on this last result; however, in a
particular application it may be advantageous to use a variation.

以下では、私たちが唯一この最後の結果に焦点を合わせるつもりです。 しかしながら、特定用途では、変化を使用するのは有利であるかもしれません。

Determining the Position of an Isolated Bit

孤立しているビットの位置を決定します。

The two obvious techniques for finding the bit position of an isolated
bit are to shift repetitively with tests, as above, and to use floating
normalization hardware.  On the PDP-10, in particular, the JFFO
instruction is made to order*.  On machines with hexadecimal
normalization, e.g. IBM 360's and XDS Sigma 7's, the normalization
hardware may not be very convenient.  A different approach uses
division and table look-up.
                                                              k
A word with a single bit on has an unsigned integer value of 2  for
                                         k
0<=k<n.  If we choose a p such that mod(2 ,p) is distinct for each

ビットが孤立しているビットの位置であることがわかるための2つの明白なテクニックは、繰返し上のテストで移行して、浮いている正常化ハードウェアを使用することです。 PDP-10では、*を命令するのをJFFO指示を特に、します。16進正常化、例えば、IBM360とXDS Sigmaのもの7があるマシンでは、正常化ハードウェアはそれほど便利でないかもしれません。 異なるアプローチは分割とテーブル索引を使用します。1ビットがオンのk A単語はk0<のための2の符号のない整数値がk<nとの等しさにします。 それぞれにおいて、私たちがpを選ぶのでモッズ(2、p)が異なるなら

0<=k<n, we can make a table of length p which gives the correspondence
             k
between mod(2 ,p) and k.  The remainder of this paper is concerned with

0 k<=<n、私たちはモッズ(2、p)とkの間で通信を与える長さpのテーブルをkにすることができます。 紙が関するこの残り

the selection of an appropriate divisor p for each word length n.

各語長nのための適切な除数pの選択。

*Some of the CDC machines have a "population count" instruction which
                                               k
gives the number of bits in a word.  Note the 2 -1 has exactly k bits

*いくつかのCDCマシンには、kが一言で言えばビットの数を与える「人口カウント」指示があります。 2 -1をちょうどkビットを持っていることに注意してください。

on.

オン。

                                                                [Page 2]

Network Working Group      A Note on Padding                      RFC 70

[2ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。

Example

   Let n = 8 and p = 11

nを8とp=11との等しさにしてください。

      Then

その時

                 0

0

            mod(2, 11)     =    1
                 1
            mod(2, 11)     =    2
                 2
            mod(2, 11)     =    4
                 3
            mod(2, 11)     =    8
                 4
            mod(2, 11)     =    5
                 5
            mod(2, 11)     =   10
                 6
            mod(2, 11)     =    9
                 7
            mod(2, 11)     =    7

10 6 5 5 8 4 4 3 2 2 1 1モッズ(2、11)=モッズ(2、11)=モッズ(2、11)=モッズ(2、11)=モッズ(2、11)=モッズ(2、11)=モッズ(2、11)は9 7モッズ(2、11)=7と等しいです。

      This yields a table of the form

これは形式のテーブルをもたらします。

         remainder             bit position

残りビット位置

             0                       --

0 --

             1                        0

1 0

             2                        1

2 1

             3                       --

3 --

             4                        2

4 2

             5                        4

5 4

             6                       --

6 --

             7                        7

7 7

             8                        3

8 3

             9                        6

9 6

            10                        5

10 5

                                                                [Page 3]

Network Working Group      A Note on Padding                      RFC 70

[3ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。

Good Divisors

良い除数

The divisor p should be as small as possible in order to minimize the

除数pができるだけわずかであるべきである、最小にする。

length of the table.  Since the divisor must generate n distinct

テーブルの長さ。 以来に除数がnを発生させなければならない、異なる。

remainders, the divisor will certainly need to be at least n.  A

確かに、残りであり、除数は、少なくともnである必要があるでしょう。 A

remainder of zero, however, can occur only if the divisor is a power of
                                               j
2.  If the divisor is a small power of 2, say 2  for j < n-1, it will

しかしながら、ゼロの残りは除数がj2のパワーである場合にだけ起こることができます。 j<n-1のための2は、除数が2のわずかなパワーであるならそうすると言います。

not generate n distinct remainders; if the divisor is a larger power of
                                       n-1     n
2, the correspondence table is either 2    or 2  in length.  We can

n異なった残りを発生させてください。 除数がn-1n2の、より大きいパワーであるなら、通信テーブルは、長さが、2か2です。 私たちはそうすることができます。

thus rule out zero as a remainder value, so the divisor must be at

したがって、残り値、除数があるに違いないそうとしてゼロを除外してください。

least one more than the word length.  This bound is in fact achieved

語長より多くの最少の1つ。 事実上、このバウンドは達成されます。

for some word lengths.

いくつかの語長のために。

Let R(p) be the number of distinct remainders p generates when divided
into successively higher powers of 2.  The distinct remainders all occur
for the R(p) lowest powers of 2.  Only odd p are interesting and the
following table gives R(p) for odd p between 1 and 21.

R(p)が2人の相次ぎより高い強国に分割されるとpが発生させる異なった残りの数であることをさせてください。 異なった残りは2人のR(p)の最も低い強国のためにすべて起こります。 変なpはおもしろいだけです、そして、以下のテーブルは変なpのためにR(p)に1と21の間与えます。

      p     R(p)                                p     R(p)

p R(p)p R(p)

      1      1                                 13     12

1 1 13 12

      3      2                                 15      4

3 2 15 4

      5      4                                 17      8

5 4 17 8

      7      3                                 19     18

7 3 19 18

      9      6                                 21      6

9 6 21 6

      11     10

11 10

This table shows that 7, 15, 17 and 21 are useless divisors because
there are smaller divisors which generate a larger number of distinct
remainders.  If we limit our attention to p such that p > p' =>
R(p) > R(p'), we obtain the following table of useful divisors for
p < 100.

より多くの異なった残りを発生させるよりわずかな除数があるので、このテーブルは、7、15、17、および21が役に立たない除数であることを示します。 '私たちの留意をそのようなp>R(p)そのp>p'=>R(p')に制限するなら、私たちは役に立つ除数の以下のテーブルをp<100に入手します。

                                                                [Page 4]

Network Working Group      A Note on Padding                      RFC 70

[4ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。

      p     R(p)                                p     R(p)

p R(p)p R(p)

      1      1                                 29     28

1 1 29 28

      3      2                                 37     36

3 2 37 36

      5      4                                 53     52

5 4 53 52

      9      6                                 59     58

9 6 59 58

      11     10                                61     60

11 10 61 60

      13     12                                67     66

13 12 67 66

      19     18                                83     82

19 18 83 82

      25     20

25 20

Notice that 9 and 25 are useful divisors even though they generate only
6 and 20 remainders, respectively.

それらは6と20残りだけをそれぞれ発生させますが、9と25が役に立つ除数であるのに注意してください。

Determination of R(p)

Rの決断(p)

If p is odd, the remainders

pが変であるなら残り

           0

0

      mod(2 ,p)
           1
      mod(2 ,p)

モッズ(2、p)1人のモッズ(2、p)

           .
           .
           .
                                                               t
will be between 1 and p-1 inclusive.  At some power of 2, say 2 , there
                                                       k    t
will be a repeated remainder, so that for some k < t, 2  = 2  mod p.
       t+1    k+1
Since 2    = 2    mod p
       t+2    k+2
and   2    = 2    mod p

… tは1とp-1の間で包括的になるでしょう。 2は、そこでは、k tが2の何らかのパワーで繰り返された残りになると言って、そうはいくらかのk<tのためのそれです、2 = 2 モッズp.t+1k+1Since2 = 2モッズp t+2k+2と2 = 2モッズp

           .
           .
           .
          etc.
                                          0    t-1
all of the distinct remainders occur for 2 ...2   .  Therefore, R(p)=t.

…など 0 異なった残りのすべてが起こるt-1 2…2 . したがって、R(p)はtと等しいです。

                                                                [Page 5]

Network Working Group      A Note on Padding                      RFC 70

[5ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。

Next we show that

次に、私たちはそれを示しています。

      R(p)
     2     = 1 mod p
                      R(p)    k
We already know that 2     = 2  mod p

R(p)2 = 1モッズp R(p)k Weは既にそんなに2 = 2にモッズpを知ります。

for some 0<=k<R(p).  Let j=R(p)-k so 0<j<=R(p).  Then

およそ0のために、<はk<R(p)と等しいです。 0<j<がR(p)と等しいようにj=R(p)-kをさせてください。 その時

      k+j           k
     2           = 2  mod p
      j  k          k
or   2 *2        = 2  mod p
       j     k
or   (2 -1)*2    =  0 mod p
                       k                                     j
Now p does not divide 2  because p is odd, so p must divide 2 -1.  Thus

pが変であるので2*2 = 2モッズp j kか(2 -1)*2 = 0モッズp k j k+j k2 = 2モッズp j k kか現在のpが2を割らないので、pは2 -1に分割されなければなりません。 このようにして

       j
      2 -1        =  0 mod p
       j
      2           =  1 mod p

j2 -1 = 0モッズp j2 = 1モッズp

Since j is greater than 0 by hypothesis and since ther is no k other
than 0 less than R(p) such that

仮説とther以来jが0以上である時から0を除いたkがないのがR(p)より少ないそのようなものである、それ

       k    0
      2  = 2  mod p,

k0 2 = 2モッズp

                         R(p)
we must have j=R(p), or 2     = 1 mod p.
                                                       k
We have thus shown that for odd p, the remainders mod(2 ,p) are unique
for k = 0, 1,..., R(p)-1 and then repeat exactly, beginning with

R(p)、2 = 1 私たちがj=R(p)を持たなければならない、その結果、さもなければ、モッズp.k Weはk=0、1に、変なpに関して、残りモッズ(2、p)がユニークであることを示しました…, R(p)-1とその時はまさに始めを繰り返します。

       R(p)
      2     = 1 mod p.

R(p)2 = 1モッズp。

We now consider even p.  Let

私たちは現在、pさえ考えます。 貸されます。

              q
      p = p'*2 ,
                                k                     k          k
where p' is odd.  For k<q, mod(2 ,p) is clearly just 2  because 2 <p.

'q pはp'*2、p'が変であるk k kと等しいです。 k<qに関しては、モッズ(2、p)が明確にただ2歳である、2<p。

For k>=q,
          k       q      k-q
     mod(2 ,p) = 2 *mod(2   ,p').

'k>=qに関して、k q k-qモッズ(2、p)は2*モッズ(2、p')と等しいです。

                                                                [Page 6]

Network Working Group      A Note on Padding                      RFC 70

[6ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。

From this we can see that the sequence of remainders will have an
                             q-1
initial segment of 1, 2, ...2    of length q, and repeating segments of

これから、私たちは、残りの系列には1、2のq-1の初期のセグメントがあるのを見ることができます…長さq、および2つの繰り返しているセグメント

length R(p').  Therefore, R(p) = q+R(p').  Since we normally expect

'の長さR(p')。 'したがって、R(p)はq+R(p')と等しいです。 以来、通常、私たちは予想します。

     R(p) ~ p,

R(p)~p

even p generally will not be useful.

一般に、pは役に立ちさえしません。

I don't know of a direct way of choosing a p for a given n, but the
previous table was generated from the following Fortran program run
under the SEX system at UCLA.

私は当然のことnのためのpを選ぶダイレクト方法を知りませんが、前のテーブルはUCLAで以下のFortranプログラム走行からSEXシステムの下で発生しました。

            0

0

                    CALL IASSGN('OC ',56)
            1       FORMAT(I3,I5)
                    M=0
                    DO 100 K=1,100,2
                    K=1
                    L=0
            20      L=L+1
                    N=MOD(2*N,K)
                    IF(N.GT.1) GO TO 20
                    IF(L.LE.M) GO TO 100
                    M=L
                    WRITE(56,1)K,L
            100     CONTINUE
                    STOP
                    END

呼び出し..形式..モッズ..行く..行く..書く..続ける..停止..終わり

      Fortran program to computer useful divisors

Fortranはコンピュータの役に立つ除数にプログラムを作ります。

In the program, K takes on trial values of p, N takes on the values of
the successive remainders, L counts up to R(p), and M remembers the
previous largest R(p).  Execution is quite speedy.

プログラム、公判中の撮影が評価するpのKでは、Nは連続した残りの値を呈します、そして、LはR(p)まで数えます、そして、Mは前の最も大きいR(p)を覚えています。 実行はかなり迅速です。

                                                                [Page 7]

Network Working Group      A Note on Padding                      RFC 70

[7ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。

Results from Number Theory

整数論からの結果

The quantity referred to above as R(p) is usually written Ord 2 and is
                                                             p
read "the order of 2 mod p".  The maximum value of Ord 2 is given by
                                                      p
Euler's phi-function, sometimes called the totient.  The totient of a

R(p)が通常、書かれたオード川2であり、pであるので上と呼ばれた量は「2モッズpの注文」を読みました。 totientは、時々オード川2の最大値がpオイラーのオイラーのファイ関数によって与えられると呼びました。 aのtotient

positive integer p is the number of integers less than p which are

正の整数pはそうするpより少ない整数の数です。

relatively prime to p.  The totient is easy to compute from a

pに比較的主要です。 totientはaから計算しやすいです。

representation of p as a product of primes:

盛りの製品としてのpの表現:

               n      n        n
     Let p = p  1 * p  2 ... p  k
              1      2        k

n n n Let pはp1*p2…p k1 2kと等しいです。

where the p  are distinct primes.  Then
           i
                          k -1               k -1                 k -1
     phi(p) = (p - 1) * p  1   * (p - 1) * p  2   ... (p - 1) * p  k
                1        1         2        2           k        k

pが異なった盛りであるところ。 次に、i k-1k-1k-1phi(p)は(p--1)*p1*(p--1)*p2と等しいです… (p--1) * p k1 1 2 2k k

If p is prime, the totient of p is simply

pが主要であるなら、pのtotientは単に主要です。

     phi(p) = p-1.

phi(p)はp-1と等しいです。

If p is not prime, the totient is smaller.

pが主要でないなら、totientは、より小さいです。

If a is relatively prime to p, then Euler's generalization of Fermat's
theorem states

aがp、フェルマーの定理州に関する当時のオイラーの一般化に比較的主要であるなら

      phi(m)
     a       = 1 mod p.

φ(m)aは1人のモッズpと等しいです。

It is this theorem which places an upper bound Ord 2, because Ord 2 is
                                                  p              p
the smallest value such that

それが上限オード川2を置くこの定理であり、オード川2が最も小さくp pであるのでそのようなものを評価してください、それ

      Ord 2
     2   p  = 1 mod p

オード川2 2pは1人のモッズpと等しいです。

Moreover it is always true that phi(p) is divisible by Ord 2.
                                                          p

そのうえ、phi(p)がオード川2pで分割可能であることは、いつも本当です。

                                                                [Page 8]

Network Working Group      A Note on Padding                      RFC 70

[8ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。

Acknowledgements

承認

Bob Kahn read an early draft and made many comments which improved the
exposition.  Alex Hurwitz assured me that a search technique is
necessary to compute R(p), and supplied the names for the quantities
and theorems I uncovered.

ボブ・カーンは、早めの草稿を読んで、博覧会を改良した多くのコメントをしました。 アレックス・ハーウィッツは、検索技術がR(p)を計算するのに必要であることを私に知らせて、私が発見した量と定理に名前を提供しました。

       [ This RFC was put into machine readable form for entry ]
       [ into the online RFC archives by Guillaume Lahaye and  ] 
                          [ John Hewes 6/97 ]

そして、[このRFCはエントリーのためのマシンに入れられた読み込み可能なフォームでした]、[ギヨームLahayeによるオンラインRFCアーカイブ、][ジョン・ヒューズ6/97]

                                                                [Page 9]

[9ページ]

一覧

 RFC 1〜100  RFC 1401〜1500  RFC 2801〜2900  RFC 4201〜4300 
 RFC 101〜200  RFC 1501〜1600  RFC 2901〜3000  RFC 4301〜4400 
 RFC 201〜300  RFC 1601〜1700  RFC 3001〜3100  RFC 4401〜4500 
 RFC 301〜400  RFC 1701〜1800  RFC 3101〜3200  RFC 4501〜4600 
 RFC 401〜500  RFC 1801〜1900  RFC 3201〜3300  RFC 4601〜4700 
 RFC 501〜600  RFC 1901〜2000  RFC 3301〜3400  RFC 4701〜4800 
 RFC 601〜700  RFC 2001〜2100  RFC 3401〜3500  RFC 4801〜4900 
 RFC 701〜800  RFC 2101〜2200  RFC 3501〜3600  RFC 4901〜5000 
 RFC 801〜900  RFC 2201〜2300  RFC 3601〜3700  RFC 5001〜5100 
 RFC 901〜1000  RFC 2301〜2400  RFC 3701〜3800  RFC 5101〜5200 
 RFC 1001〜1100  RFC 2401〜2500  RFC 3801〜3900  RFC 5201〜5300 
 RFC 1101〜1200  RFC 2501〜2600  RFC 3901〜4000  RFC 5301〜5400 
 RFC 1201〜1300  RFC 2601〜2700  RFC 4001〜4100  RFC 5401〜5500 
 RFC 1301〜1400  RFC 2701〜2800  RFC 4101〜4200 

スポンサーリンク

FLOOR関数 最大の整数値(小数点以下の切捨て)

ホームページ製作・web系アプリ系の製作案件募集中です。

上に戻る