Aufgaben:Aufgabe 5.4Z: OVSF–Codes: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
K (Textersetzung - „*Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.“ durch „ “)
 
(5 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID1891__Mod_Z_5_4.png|right|frame|Baumstruktur zur Konstruktion eines OVSF–Codes]]
+
[[Datei:P_ID1891__Mod_Z_5_4.png|right|frame|Zur Konstruktion <br>eines OVSF–Codes]]
Die Spreizcodes für [[Beispiele_von_Nachrichtensystemen/Allgemeine_Beschreibung_von_UMTS|UMTS]] sollen  
+
Die Spreizcodes für &nbsp;[[Beispiele_von_Nachrichtensystemen/Allgemeine_Beschreibung_von_UMTS|UMTS]]&nbsp; sollen  
* alle zueinander orthogonal sein, um eine gegenseitige Beeinflussung der Teilnehmer zu vermeiden,
+
* alle zueinander orthogonal sein,&nbsp; um eine gegenseitige Beeinflussung der Teilnehmer zu vermeiden,
* zusätzlich eine flexible Realisierung unterschiedlicher Spreizfaktoren J ermöglichen.
+
* zusätzlich eine flexible Realisierung unterschiedlicher Spreizfaktoren &nbsp;$J$&nbsp; ermöglichen.
  
Ein Beispiel hierfür sind die so genannten  [[Modulationsverfahren/Spreizfolgen_für_CDMA#Codes_mit_variablem_Spreizfaktor_.28OVSF.E2.80.93Code.29|Codes mit variablem Spreizfaktor]] (englisch: ''Orthogonal Variable Spreading'' Factor, OVSF), die Spreizcodes der Längen von $J = 4$ bis $J = 512$ bereitstellen. Diese können, wie in der Grafik zu sehen ist, mit Hilfe eines Codebaums erstellt werden. Dabei entstehen bei jeder Verzweigung aus einem Code $C$ zwei neue Codes $+C \ +C$ und $+C \ -C$.
 
  
 +
Ein Beispiel hierfür sind die so genannten&nbsp;[[Modulationsverfahren/Spreizfolgen_für_CDMA#Codes_mit_variablem_Spreizfaktor_.28OVSF.E2.80.93Code.29|Codes mit variablem Spreizfaktor]]&nbsp; $($englisch:&nbsp; "Orthogonal Variable Spreading Factor",&nbsp; $\rm OVSF)$,&nbsp; die Spreizcodes der Längen von &nbsp;$J = 4$&nbsp; bis &nbsp;$J = 512$&nbsp; bereitstellen.
  
Die Grafik verdeutlicht das hier angegebene Prinzip am Beispiel $J = 4$. Nummeriert man die Spreizfolgen von $0$ bis $J -1$ durch, so ergeben sich hier die Spreizfolgen
+
Diese können,&nbsp; wie in der Grafik zu sehen ist,&nbsp; mit Hilfe eines Codebaums erstellt werden.&nbsp; Dabei entstehen bei jeder Verzweigung aus einem Code &nbsp; $C$&nbsp; zwei neue Codes &nbsp;$(+C \ +C)$&nbsp; und &nbsp;$(+C \ -C)$.
 +
 
 +
Die Grafik verdeutlicht das hier angegebene Prinzip am Beispiel &nbsp;$J = 4$:&nbsp;
 +
*Nummeriert man die Spreizfolgen von &nbsp;$0$&nbsp; bis &nbsp;$J -1$&nbsp; durch,&nbsp; so ergeben sich hier die Spreizfolgen
 
:$$\langle c_\nu^{(0)}\rangle  =  {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm} {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.05cm},\hspace{0.3cm} \langle c_\nu^{(1)}\rangle = {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm} {-\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.05cm},$$  
 
:$$\langle c_\nu^{(0)}\rangle  =  {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm} {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.05cm},\hspace{0.3cm} \langle c_\nu^{(1)}\rangle = {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm} {-\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.05cm},$$  
 
:$$\langle c_\nu^{(2)}\rangle  =  {+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.15cm} {+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.05cm},\hspace{0.3cm} \langle c_\nu^{(3)}\rangle = {+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.15cm} {-\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.05cm}.$$
 
:$$\langle c_\nu^{(2)}\rangle  =  {+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.15cm} {+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.05cm},\hspace{0.3cm} \langle c_\nu^{(3)}\rangle = {+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.15cm} {-\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.05cm}.$$
Entsprechend dieser Nomenklatur gibt es für den Spreizfaktor $J = 8$ die Spreizfolgen $\langle c_\nu^{(0)}\rangle $, ... , $\langle c_\nu^{(7)}\rangle $.
+
*Entsprechend dieser Nomenklatur gibt es für den Spreizfaktor &nbsp;$J = 8$&nbsp; die Spreizfolgen &nbsp;$\langle c_\nu^{(0)}\rangle $, ... , $\langle c_\nu^{(7)}\rangle $.
  
Anzumerken ist, dass kein Vorgänger und Nachfolger eines Codes für einen anderen Teilnehmer benutzt werden darf. Im Beispiel könnten also vier Spreizcodes mit Spreizfaktor $J = 4$ verwendet werden oder die drei gelb hinterlegten Codes – einmal mit $J = 2$ und zweimal mit $J = 4$.
+
*Anzumerken ist, dass kein Vorgänger und Nachfolger eines Codes für einen anderen Teilnehmer benutzt werden darf.  
 +
*Im Beispiel könnten also vier Spreizcodes mit Spreizfaktor &nbsp;$J = 4$&nbsp; verwendet werden oder die drei gelb hinterlegten Codes – einmal mit &nbsp;$J = 2$&nbsp; und zweimal mit &nbsp;$J = 4$.
  
  
  
''Hinweise:''
+
 
*Die Aufgabe gehört zum  Kapitel [[Modulationsverfahren/Spreizfolgen_für_CDMA|Spreizfolgen für CDMA]].
+
 
*Bezug genommen wird insbesondere auf den Abschnitt [[Modulationsverfahren/Spreizfolgen_für_CDMA#Codes_mit_variablem_Spreizfaktor_.28OVSF.E2.80.93Code.29 |Codes mit variablem Spreizfaktor]] im Theorieteil.  
+
 
* Wir möchten Sie gerne auch auf das Interaktionsmodul [[OVSF]] hinweisen.
+
Hinweise:  
 +
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Modulationsverfahren/Spreizfolgen_für_CDMA|Spreizfolgen für CDMA]].
 +
*Bezug genommen wird insbesondere auf den Abschnitt&nbsp; [[Modulationsverfahren/Spreizfolgen_für_CDMA#Codes_mit_variablem_Spreizfaktor_.28OVSF.E2.80.93Code.29 |Codes mit variablem Spreizfaktor]]&nbsp; im Theorieteil.  
 +
* Wir möchten Sie gerne auch auf das kleine interaktive SWF&ndash;Applet &nbsp;[[Applets:OVSF-Codes_(Applet)|OVSF]]&nbsp; hinweisen.
 
   
 
   
  
Zeile 30: Zeile 37:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Konstruieren Sie das Baumdiagramm für $J = 8$. Welche OVSF–Codes ergeben sich daraus?
+
{Konstruieren Sie das Baumdiagramm für &nbsp;$J = 8$.&nbsp; Welche OVSF–Codes ergeben sich daraus?
 
|type="[]"}
 
|type="[]"}
 
+ '''Codewort 1:''' &nbsp; $ \langle c_\nu^{(1)}\rangle  =  {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm} {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm}{-\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.15cm}{-\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.05cm},$
 
+ '''Codewort 1:''' &nbsp; $ \langle c_\nu^{(1)}\rangle  =  {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm} {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm}{-\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.15cm}{-\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.05cm},$
Zeile 38: Zeile 45:
  
  
{Wieviele UMTS–Teilnehmer $(K_{\rm max})$ können mit $J = 8$ maximal bedient werden?
+
{Wieviele UMTS–Teilnehmer &nbsp;$(K_{\rm max})$&nbsp; können mit &nbsp;$J = 8$&nbsp; maximal bedient werden?
 
|type="{}"}
 
|type="{}"}
 
$K_{\rm max} \ = \ $ { 8 }
 
$K_{\rm max} \ = \ $ { 8 }
  
{Wieviele Teilnehmer $(K)$ können versorgt werden, wenn drei dieser Teilnehmer einen Spreizcode mit $J = 4$ verwenden sollen?
+
{Wieviele Teilnehmer &nbsp;$(K)$&nbsp; können versorgt werden,&nbsp; wenn drei dieser Teilnehmer einen Spreizcode mit &nbsp;$J = 4$&nbsp; verwenden sollen?
 
|type="{}"}
 
|type="{}"}
 
$K \ = \ $ { 5 }  
 
$K \ = \ $ { 5 }  
  
{Gehen Sie von einer Baumstruktur für $J = 32$ aus.  
+
{Gehen Sie von einer Baumstruktur für &nbsp;$J = 32$&nbsp; aus.&nbsp; Ist die folgende Zuweisung machbar: <br>Zweimal &nbsp;$J = 4$,&nbsp; einmal &nbsp;$J = 8$,&nbsp; zweimal &nbsp;$J = 16$&nbsp; und&nbsp; achtmal &nbsp;$J = 32$?
<br>Ist die folgende Zuweisung machbar: Zweimal $J = 4$, einmal $J = 8$, zweimal $J = 16$ und achtmal $J = 32$?
+
|type="()"}
|type="[]"}
 
 
+ Ja.
 
+ Ja.
 
- Nein.
 
- Nein.
Zeile 55: Zeile 61:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
[[Datei:P_ID1892__Mod_Z_5_4a.png|right|frame|OVSF–Baumstruktur für <i>J</i> = 8]]
+
[[Datei:P_ID1892__Mod_Z_5_4a.png|right|frame|OVSF–Baumstruktur für &nbsp;$J = 8$]]
'''(1)'''&nbsp; Die Grafik zeigt die OVSF–Baumstruktur für $J = 8$ Nutzer. Daraus ist ersichtlich, dass die<u> Lösungsvorschläge 1, 3 und 4</u> zutreffen, nicht jedoch der zweite.
+
'''(1)'''&nbsp; Die Grafik zeigt die OVSF–Baumstruktur für &nbsp;$J = 8$.&nbsp; Daraus ist zu erkennen,&nbsp; dass die&nbsp; <u> Lösungsvorschläge 1, 3 und 4</u>&nbsp; zutreffen,&nbsp; nicht jedoch der zweite.
  
  
'''(2)'''&nbsp; Wird jedem Nutzer ein Spreizcode mit $J = 8$ zugewiesen, so können $K_{\rm max}\hspace{0.15cm}\underline{ = 8}$ Teilnehmer versorgt werden.
+
'''(2)'''&nbsp; Wird jedem Nutzer ein Spreizcode mit&nbsp; $J = 8$&nbsp; zugewiesen,&nbsp; so können&nbsp; $K_{\rm max}\hspace{0.15cm}\underline{ = 8}$&nbsp; Teilnehmer versorgt werden.
  
  
'''(3)'''&nbsp; Wenn drei Teilnehmer mit $J = 4$ versorgt werden, können nur mehr zwei Teilnehmer durch eine Spreizfolge mit $J = 8$ bedient werden (siehe beispielhafte gelbe Hinterlegung in obiger Grafik) &nbsp; ⇒ &nbsp; $K\hspace{0.15cm}\underline{ = 5}$.
+
'''(3)'''&nbsp; Wenn drei Teilnehmer mit&nbsp; $J = 4$&nbsp; versorgt werden,&nbsp; können nur mehr zwei Teilnehmer durch eine Spreizfolge mit&nbsp; $J = 8$&nbsp; bedient werden&nbsp; (siehe beispielhafte gelbe Hinterlegung in der Grafik) &nbsp; ⇒ &nbsp; $K\hspace{0.15cm}\underline{ = 5}$.
  
  
 
'''(4)'''&nbsp; Wir bezeichnen mit
 
'''(4)'''&nbsp; Wir bezeichnen mit
* $K_4 = 2$ die Anzahl der Spreizfolgen mit $J = 4$,
+
* $K_4 = 2$&nbsp; die Anzahl der Spreizfolgen mit&nbsp; $J = 4$,
* $K_8 = 1$ die Anzahl der Spreizfolgen mit $J = 8$,
+
* $K_8 = 1$&nbsp; die Anzahl der Spreizfolgen mit&nbsp; $J = 8$,
* $K_{16} = 2$ die Anzahl der Spreizfolgen mit $J = 16$,
+
* $K_{16} = 2$&nbsp; die Anzahl der Spreizfolgen mit&nbsp; $J = 16$,
* $K_{32} = 8$ die Anzahl der Spreizfolgen mit $J = 32$.
+
* $K_{32} = 8$&nbsp; die Anzahl der Spreizfolgen mit&nbsp; $J = 32$.
  
  
Zeile 76: Zeile 82:
 
\Rightarrow \hspace{0.3cm} K_4 \cdot8 + K_8 \cdot 4 +K_{16} \cdot 2 +K_{32} \cdot1 \le 32 \hspace{0.05cm}.$$
 
\Rightarrow \hspace{0.3cm} K_4 \cdot8 + K_8 \cdot 4 +K_{16} \cdot 2 +K_{32} \cdot1 \le 32 \hspace{0.05cm}.$$
  
*Wegen 2 · 8 + 1 · 4 + 2 · 2 + 8 = 32 ist die gewünschte Belegung gerade noch erlaubt &nbsp; ⇒ &nbsp; <u>Antwort JA</u>.  
+
*Wegen &nbsp; $2 · 8 + 1 · 4 + 2 · 2 + 8 = 32$ &nbsp; ist die gewünschte Belegung gerade noch erlaubt &nbsp; ⇒ &nbsp; <u>Antwort JA</u>.  
*Die zweimalige Bereitstellung des Spreizgrads $J = 4$ blockiert zum Beispiel die obere Hälfte des Baums.
+
*Die zweimalige Bereitstellung des Spreizgrads &nbsp;$J = 4$&nbsp; blockiert zum Beispiel die obere Hälfte des Baums.
*Nach der Versorgung der einen Spreizung mit $J = 8$, bleiben auf der $J = 8$–Ebene noch drei der acht Äste zu belegen, usw. und so fort.
+
*Nach der Versorgung der einen Spreizung mit &nbsp;$J = 8$,&nbsp; bleiben auf der &nbsp;$J = 8$–Ebene noch drei der acht Äste zu belegen, usw. und so fort.
  
 
{{ML-Fuß}}
 
{{ML-Fuß}}

Aktuelle Version vom 13. Dezember 2021, 16:38 Uhr

Zur Konstruktion
eines OVSF–Codes

Die Spreizcodes für  UMTS  sollen

  • alle zueinander orthogonal sein,  um eine gegenseitige Beeinflussung der Teilnehmer zu vermeiden,
  • zusätzlich eine flexible Realisierung unterschiedlicher Spreizfaktoren  $J$  ermöglichen.


Ein Beispiel hierfür sind die so genannten Codes mit variablem Spreizfaktor  $($englisch:  "Orthogonal Variable Spreading Factor",  $\rm OVSF)$,  die Spreizcodes der Längen von  $J = 4$  bis  $J = 512$  bereitstellen.

Diese können,  wie in der Grafik zu sehen ist,  mit Hilfe eines Codebaums erstellt werden.  Dabei entstehen bei jeder Verzweigung aus einem Code   $C$  zwei neue Codes  $(+C \ +C)$  und  $(+C \ -C)$.

Die Grafik verdeutlicht das hier angegebene Prinzip am Beispiel  $J = 4$: 

  • Nummeriert man die Spreizfolgen von  $0$  bis  $J -1$  durch,  so ergeben sich hier die Spreizfolgen
$$\langle c_\nu^{(0)}\rangle = {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm} {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.05cm},\hspace{0.3cm} \langle c_\nu^{(1)}\rangle = {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm} {-\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.05cm},$$
$$\langle c_\nu^{(2)}\rangle = {+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.15cm} {+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.05cm},\hspace{0.3cm} \langle c_\nu^{(3)}\rangle = {+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.15cm} {-\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.05cm}.$$
  • Entsprechend dieser Nomenklatur gibt es für den Spreizfaktor  $J = 8$  die Spreizfolgen  $\langle c_\nu^{(0)}\rangle $, ... , $\langle c_\nu^{(7)}\rangle $.
  • Anzumerken ist, dass kein Vorgänger und Nachfolger eines Codes für einen anderen Teilnehmer benutzt werden darf.
  • Im Beispiel könnten also vier Spreizcodes mit Spreizfaktor  $J = 4$  verwendet werden oder die drei gelb hinterlegten Codes – einmal mit  $J = 2$  und zweimal mit  $J = 4$.




Hinweise:


Fragebogen

1

Konstruieren Sie das Baumdiagramm für  $J = 8$.  Welche OVSF–Codes ergeben sich daraus?

Codewort 1:   $ \langle c_\nu^{(1)}\rangle = {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm} {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm}{-\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.15cm}{-\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.05cm},$
Codewort 3:   $ \langle c_\nu^{(3)}\rangle = {+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm} {-\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.15cm}{+\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm}{-\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1}$ ,
Codewort 5:   $ \langle c_\nu^{(5)}\rangle = {+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.15cm} {+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.15cm}{+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.15cm}{+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.05cm}$,
Codewort 7:   $ \langle c_\nu^{(7)}\rangle = {+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.15cm} {-\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm}{-\hspace{-0.05cm}1}\hspace{0.15cm} {+\hspace{-0.05cm}1} \hspace{0.15cm}{+\hspace{-0.05cm}1}\hspace{0.15cm} {-\hspace{-0.05cm}1} \hspace{0.05cm}$.

2

Wieviele UMTS–Teilnehmer  $(K_{\rm max})$  können mit  $J = 8$  maximal bedient werden?

$K_{\rm max} \ = \ $

3

Wieviele Teilnehmer  $(K)$  können versorgt werden,  wenn drei dieser Teilnehmer einen Spreizcode mit  $J = 4$  verwenden sollen?

$K \ = \ $

4

Gehen Sie von einer Baumstruktur für  $J = 32$  aus.  Ist die folgende Zuweisung machbar:
Zweimal  $J = 4$,  einmal  $J = 8$,  zweimal  $J = 16$  und  achtmal  $J = 32$?

Ja.
Nein.


Musterlösung

OVSF–Baumstruktur für  $J = 8$

(1)  Die Grafik zeigt die OVSF–Baumstruktur für  $J = 8$.  Daraus ist zu erkennen,  dass die  Lösungsvorschläge 1, 3 und 4  zutreffen,  nicht jedoch der zweite.


(2)  Wird jedem Nutzer ein Spreizcode mit  $J = 8$  zugewiesen,  so können  $K_{\rm max}\hspace{0.15cm}\underline{ = 8}$  Teilnehmer versorgt werden.


(3)  Wenn drei Teilnehmer mit  $J = 4$  versorgt werden,  können nur mehr zwei Teilnehmer durch eine Spreizfolge mit  $J = 8$  bedient werden  (siehe beispielhafte gelbe Hinterlegung in der Grafik)   ⇒   $K\hspace{0.15cm}\underline{ = 5}$.


(4)  Wir bezeichnen mit

  • $K_4 = 2$  die Anzahl der Spreizfolgen mit  $J = 4$,
  • $K_8 = 1$  die Anzahl der Spreizfolgen mit  $J = 8$,
  • $K_{16} = 2$  die Anzahl der Spreizfolgen mit  $J = 16$,
  • $K_{32} = 8$  die Anzahl der Spreizfolgen mit  $J = 32$.


Dann muss folgende Bedingung erfüllt sein:

$$K_4 \cdot \frac{32}{4} + K_8 \cdot \frac{32}{8} +K_{16} \cdot \frac{32}{16} +K_{32} \cdot \frac{32}{32} \le 32 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} K_4 \cdot8 + K_8 \cdot 4 +K_{16} \cdot 2 +K_{32} \cdot1 \le 32 \hspace{0.05cm}.$$
  • Wegen   $2 · 8 + 1 · 4 + 2 · 2 + 8 = 32$   ist die gewünschte Belegung gerade noch erlaubt   ⇒   Antwort JA.
  • Die zweimalige Bereitstellung des Spreizgrads  $J = 4$  blockiert zum Beispiel die obere Hälfte des Baums.
  • Nach der Versorgung der einen Spreizung mit  $J = 8$,  bleiben auf der  $J = 8$–Ebene noch drei der acht Äste zu belegen, usw. und so fort.